11、数据结构——栈与队列——队列的顺序实现（二）

一、方式一

结构体定义(方式一)

1
2
3
4
5
#define MaxSize 10
typedef struct {
    ElemType data[MaxSize];
    int front, rear;
} SqQueue;

初始化队列(方式一)

1
2
3
void InitQueue(SqQueue &Q) {
	Q.rear = Q.front = 0;
}

队列判空(方式一)

1
2
3
bool Empty(SqQueue &Q) {
    return Q.rear == Q.front;
}

队列入队(方式一)

1
2
3
4
5
6
bool EnQueue(SqQueue &Q, ElemType x) {
    if ((Q.rear + 1) % MaxSize == Q.front) return false;
    Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}
image-20240217181144935

队列出队(方式一)

1
2
3
4
5
6
bool DeQueue(SqQueue &Q,ElemType &x) {
    if (Q.rear == Q.front) return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

获取队列队头元素(方式一)

1
2
3
4
5
bool GetHead(SqQueue Q,ElemType &x) {
    if (Q.rear == Q.front) return false;
    x = Q.data[Q.front];
    return true;
}

二、方式二

结构体定义(方式二)

1
2
3
4
5
6
#define MaxSize 10
typedef struct {
    ElemType data[MaxSize];
    int front, rear;
    int size;
} SqQueue;

初始化队列(方式二)

1
2
3
void InitQueue(SqQueue &Q) {
	Q.rear = Q.front = 0;
}

队列判空(方式二)

1
2
3
bool Empty(SqQueue &Q) {
    return Q.size == 0;
}

队列入队(方式二)

1
2
3
4
5
6
bool EnQueue(SqQueue &Q, ElemType x) {
    if (Q.size == MaxSize) return false;
    Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}
image-20240217181144935

队列出队(方式二)

1
2
3
4
5
6
bool DeQueue(SqQueue &Q,ElemType &x) {
    if (Q.size == 0) return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

获取队列队头元素(方式二)

1
2
3
4
5
bool GetHead(SqQueue Q,ElemType &x) {
    if (Q.size() == 0) return false;
    x = Q.data[Q.front];
    return true;
}

三、方式三

结构体定义(方式三)

1
2
3
4
5
6
#define MaxSize 10
typedef struct {
    ElemType data[MaxSize];
    int front, rear;
    int tag; // 每次删除操作都令tag = 0；每次插入操作都令tag = 1.
} SqQueue;

初始化队列(方式三)

1
2
3
void InitQueue(SqQueue &Q) {
	Q.rear = Q.front = Q.tag= 0;
}

队列判空(方式三)

1
2
3
bool Empty(SqQueue &Q) {
    return Q.front == Q.rear && tag == 0;
}

队列入队(方式三)

1
2
3
4
5
6
bool EnQueue(SqQueue &Q, ElemType x) {
    if (Q.front == Q.rear && Q.tag == 1) return false;
    Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}
image-20240217181144935

队列出队(方式三)

1
2
3
4
5
6
bool DeQueue(SqQueue &Q,ElemType &x) {
    if (Q.tag == 0 && Q.rear == Q.front) return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

获取队列队头元素(方式三)

1
2
3
4
5
bool GetHead(SqQueue Q,ElemType &x) {
    if (Q.tag == 0 && Q.rear == Q.front) return false;
    x = Q.data[Q.front];
    return true;
}

四、其他

​ 考试的时候可能它的rear和front的执行会有所不同，这时候代码编写就会有一点点差异，需要灵活变化了。

下一节内容是：12、栈与队列——队列的链式实现！！！

一定要把本节内容看懂再往下看，不然会非常痛苦的哦o(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)o……..