牺牲一个存储单元来判断队满。
#include<iostream>
using namespace std;
// 循环队列
#define MaxSize 10
typedef int ElemType;
typedef struct {ElemType data[MaxSize];int front, rear;
} SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q) {// 判断队空 Q.rear == Q.frontQ.front = Q.rear = 0;
}
// 入队
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;
}
// 出队
bool DeQueue(SqQueue &Q, ElemType &x) {if (Q.front == Q.rear) {return false;}x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;return true;
}
// 遍历
void Traverse(SqQueue Q) {for (int i = Q.front; i < Q.rear; i++) {cout << Q.data[i] << " ";}cout << endl;
}
// 长度
int QueueLength(SqQueue Q) {return (Q.rear - Q.front + MaxSize) % MaxSize;
}
int main() {SqQueue Q;InitQueue(Q);ElemType x;EnQueue(Q, 1);EnQueue(Q, 2);EnQueue(Q, 3);EnQueue(Q, 4);DeQueue(Q, x);cout << "出队元素为:" << x << endl;cout << "队列长度为:" << QueueLength(Q) << endl;Traverse(Q);return 0;
}
特殊地,如果队尾指针指向的是队尾元素:
// 判断空
// 队尾指针的后一个位置就是队头指针
(Q.rear + 1) % MaxSize == Q.front
// 判断满
// 队尾指针的后两个位置就是队头指针,后一个位置为空
当然,还可以加一个变量比如 size
或者 tag
来进行判断。