大家好，又见面了，我是你们的朋友全栈君。
顺序存储结构
所谓顺序存储结构就是用一组地址连续的存储单元依次存放从队头到队尾的元素。
声明两个指针rear、front分别用来指示队尾元素的下一位置和队头元素的位置。
初始化时rear = front = 0
，插入新的元素时尾指针加1，元素出队列时队头指针加1。
不过这样做有个问题，不论是入队还是出队，队头或队尾指针都是加1，这样做有一个问题，就是元素出队所空出的空间无法被重新利用了。
尽管队列中实际存储的元素个数远远小于存储空间的规模，但是仍不能做入队操作。这种现象称为假上溢。
循环队列
循环队列是队列的顺序存储结构的一种实现方式。它通过将顺序队列想象为一个首尾相接的圆环，来克服假上溢的问题。
循环队列中无法通过头尾指针相同来判断队列的状态究竟为空还是满，因为这种情况下可能为空也可能为满。
循环队列中通过少用一个元素的空间，以“头指针在尾指针的下一位置时”作为队列为满的判断标志。
代码实现
#define MAXQSIZE 100 //队列最大长度
typedef struct{
int *base; //动态分配存储空间
int front; //头指针，若队列不空指向队首元素
int rear; //尾指针，指向队尾元素的下一位置
int queueSize;
} SqQueue;
bool initQueue(SqQueue &Q, int maxSize){
Q.base = new int[maxSize];
if(!Q.base){exit(-1);}
Q.queueSize = maxSize;
Q.front = Q.rear = 0;
return true;
}
bool enQueue(SqQueue &Q, int e){
if((Q.rear + 1) % Q.queueSize == Q.front){
return false;
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % Q.queueSize;
return true;
}
bool deQueue(SqQueue &Q, int &e){
if(Q.front == Q.rear){
return false;
}
e = Q.base[Q.front];
Q.front = (Q.front + 1) % Q.queueSize;
return true;
}
注意
- 如果
rear = front，则可以判断队列为空 - 如果
(rear + 1) % size == front，则可判断队列已满 (rear - front + size) % size为队列长度
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/137178.html原文链接：https://javaforall.net
