1.由于是顺序队列,很容易想到用数组来存储元素,假如一个队列的长度是10,就是一下可以放入10个元素,当9个元素出队后,又放入3个元素,此时是不是要再增长数组的长度呢?实际中不可能增加数组的长度而任内存空间的浪费,所以我们要构造循环队列,也就是当rear=(队列的长度-1),rear=(rear+1)%(队列的长度),同理front也是如此。只要是顺序队列都是循环队列。
2.如何判断什么时候队列是空,什么时候队列已经满了呢?这个是实际中不可避免的问题。在顺序队列中,我们通常用front,rear两个"指针"来进行入队和出队的操作,在队列的初始化时,front=rear,此时队列为空,这是队列为空的判断条件;那么什么时候队列满了呢,通常留一个存储空间不存储元素,此时判断队列满的条件就是(rear+1)%(队列的长度) = front,解决了当rear = front时,不知道是队满还是队空的问题。
简单的介绍了循环队列中的棘手的问题,下面给出简单实现的代码:
点击(此处)折叠或打开
- #include<iostream>
- #define MAX_SIZE 10
- using namespace std;
-
struct Squeue {
- int data[MAX_SIZE];
- int rear, front;
- };
- void initSqueue(Squeue *);
- void emptySqueue(Squeue *);
- void fullSqueue(Squeue *);
- void Insqueue(Squeue *, int);
- void Outsqueue(Squeue *, int *);
- void ergodicSqueue(Squeue *);
- void initSqueue(Squeue *q) {
- q->front = 0;
- q->rear = 0;
- }
- void emptySqueue(Squeue *q) {
- if (q->rear == q->front) { //判断队列空的条件
- cout << "队列为空!!!" << endl;
- exit(-1);
- }
- else
- return;
- }
- void fullSqueue(Squeue *q) {
- if ((q->rear + 1) % MAX_SIZE == q->front){ //判断队列已满的条件
- cout << "队列已满!!!" << endl;
- exit(-1);
- }
- else
- return;
- }
- void Insqueue(Squeue *q, int e) {
- fullSqueue(q); //入队时判断队列是否已满
- q->data[q->rear] = e;
- q->rear = (q->rear + 1) % MAX_SIZE;
- }
- void Outsqueue(Squeue *q, int *e) {
- emptySqueue(q); //出队时判断队列是否已空
- *e = q->data[q->front];
- q->front = (q->front + 1) % MAX_SIZE;
- }
- void ergodicSqueue(Squeue *q) { //对队列进行入队出队操作后,打印在队列中的元素
- int i = 0;
- cout << "在队列中的元素是:";
- while (q->front != q->rear) {
- cout << q->data[q->front] << ",";
- q->front = (q->front + 1) % MAX_SIZE;
- i++;
- }
- cout << endl;
- cout << "队列中的元素个数为:" << i << endl; //统计队列中元素的个数
- }
-
int main() {
- Squeue queue;
- int e = 0;
- initSqueue(&queue);
- for (int i = 1; i <= 9; i++) {
- Insqueue(&queue, i);
- }
- Outsqueue(&queue, &e);
- cout << "出队的元素是:" << e << endl;
- Outsqueue(&queue, &e);
- cout << "出队的元素是:" << e << endl;
- Insqueue(&queue, 10);
- Outsqueue(&queue, &e);
- cout << "出队的元素是:" << e << endl;
- ergodicSqueue(&queue);
- }
以上只是粗略的介绍,当然更为详细的是画图分析该过程,由于画图比较繁琐,这里不作展示。