在队列的顺序存储中,采用第二种出队的方式,将头指针 +1 ,可以避免元素的移动,但是这样也出现了一个问题 "假溢出" ,如图:

当出现这种情况时:头指针和尾指针都指向了不可访问的地方(越界了),就无法在插入(入队)了,队列的空间还空着,却无法利用,这造成了空间的浪费。
为了使用到完全的空间(利用前面的空间),可以使用循环队列。(红色代表已经利用的空间)

如图,当 tail 的值为5时,他应该指向下标为 0 的空间,也就是将 tail 赋值为0。这样队列就首尾相连,变成了循环队列。
由于 头指针和尾指针的范围是 [ 0 , MAX_SIZE -1 ] ,一旦等于MAX_SIZE,就变为0,所以可以使用到取模操作,每次移动完,再对 MAX_SIZE 取模。

那出现下面这种情况还可以插入元素吗?如下图:

假如可以的话,再插入一个元素,那 tail +1 就为 3 ,这时会发现一个问题:该如何判断队列为空,如何判断队列满了,有些困难。
所以这种情况就无法再插入元素了,我们能使用到的空间只有 MAX_SIZE-1 个,其中一块空间是为了方便判断队列的状态,并不保存任何数据。
判断队列为空的条件是:头指针与尾指针指向同一个位置;判断队列为满的条件是:尾指针的后一位是头指针。
tail == head 为判空条件,结合之前的移动问题,所以不是 tail + 1 == head,而是 (tail + 1) % MAX_SIZE == head 为判满条件
如图( front 是头指针,rear 是尾指针):

顺序队列中求元素个数的方法为 尾指针减去头指针 ,可是现在有两种情况:
一、头指针在尾指针的前面(tail >= head):元素个数为 tail - head
二、尾指针在头指针的前面(tail
取模操作可以将两种情况统一为一种:元素个数为 (head - tail + MAX_SIZE) % MAX_SIZE
就是顺序队列改动了一下需要注意的点。
- #include <iostream>
-
- using namespace std;
-
- //循环队列的定义
- #define MAX_SIZE 5
- typedef int DateElem;
-
- typedef struct Queue
- {
- DateElem date[MAX_SIZE];
- int head; //头指针
- int tail; //尾指针
- }squeue;
-
- //初始化循环队列
- void InitQueue(squeue* sq)
- {
- if (!sq) return;
- sq->head = 0;
- sq->tail = 0;
- }
-
-
- //判断循环队列是否满了
- bool IsFull(squeue* sq)
- {
- if (!sq) return false;
- if ((sq->tail+1)%MAX_SIZE == sq->head) //*
- {
- return true;
- }
- else
- {
- return false;
- }
- }
- //判断循环队列是否为空
- bool IsEmpty(squeue* sq)
- {
- if (!sq) return false;
-
- if (sq->head == sq->tail)
- {
- return true;
- }
- else
- {
- return false;
- }
- }
-
- //循环队列入队
- bool EnterQueue(squeue* sq, DateElem e)
- {
- if (IsFull(sq))
- {
- cout << "无法插入元素" << e << ",队列已满。" << endl;
- return false;
- }
-
- sq->date[sq->tail] = e;
- sq->tail = (sq->tail + 1) % MAX_SIZE; //*
- return true;
- }
- //循环队列出队
- bool PopQueue(squeue* sq, DateElem* date)
- {
- if (!sq || IsEmpty(sq))
- {
- return false;
- }
-
- *date = sq->date[sq->head];
- sq->head = (sq->head + 1) % MAX_SIZE; //*
- return true;
- }
-
- //打印队列
- bool PrintQueue(squeue* sq)
- {
- if (!sq) return false;
-
- for (int i = sq->head; i != sq->tail; i = (i+1) %MAX_SIZE) //*
- {
- printf("%d ", sq->date[i]);
- }
- return true;
- }
-
- //获取队首元素
- int GetHeadElem(squeue* sq)
- {
- if (!sq || IsEmpty(sq)) return 0;
-
- return sq->date[sq->head];
- }
-
-
- //销毁(清空)队列
- bool DestoryQueue(squeue* sq)
- {
- if (!sq) return false;
-
- sq->head = 0;
- sq->tail = 0;
- return true;
- }
-
- //获取队列长度
- int GetLength(squeue* sq)
- {
- if (!sq) return 0;
-
- return (sq->tail - sq->head + MAX_SIZE) % MAX_SIZE; //*
- }
- int main(void)
- {
- squeue* sq = new squeue;
- DateElem* s = new DateElem;
- InitQueue(sq);
- DateElem e = 0;
-
- int choose = -1;
- while (choose != 0)
- {
- cout << "1.入队" << endl
- << "2.出队" << endl
- << "3.打印队列" << endl
- << "4.获取队首元素" << endl
- << "5.获取队列长度" << endl
- << "6.销毁队列" << endl
- << "0.退出" << endl;
- cin >> choose;
- switch (choose)
- {
- case 1:
- cout << "请输入要入队的元素:";
- cin >> e;
- if (EnterQueue(sq, e))
- {
- cout << "入队成功" << endl;
- }
- else
- {
- cout << "入队失败" << endl;
- }
- break;
- case 2:
- if (PopQueue(sq, s))
- {
- cout << "出队的元素是:" << *s << endl;
- }
- else
- {
- cout << "出队失败" << endl;
- }
- break;
- case 3:
- cout << "队列中的元素是:";
- PrintQueue(sq);
- cout << endl;
- break;
- case 4:
- cout << "队首元素是:" << GetHeadElem(sq) << endl;
- break;
- case 5:
- cout << "队列的长度是:" << GetLength(sq) << endl;
- break;
- case 6:
- if (DestoryQueue(sq))
- {
- cout << "队列已销毁" << endl;
- }
- else
- {
- cout << "队列不存在" << endl;
- }
- break;
- case 0:
- cout << "退出成功" << endl;
- break;
- default:
- cout << "输入非法" << endl;
- break;
-
- }
- }
- return 0;
- }