数据结构:队列的顺序存储结构(循环队列)

时间:2021-01-21 17:38:30

队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。是一种先进先出的线性表(FIFO)。允许插入的一端称为队尾,允许删除的一端称为队头。我们在《栈的顺序存储结构》中发现,栈操作的top指针在Push时增大而在Pop时减小,栈空间是可以重复利用的,而队列的front、rear指针都在一直增大,虽然前面的元素已经出队了,但它所占的存储空间却不能重复利用。但大多数程序并不是这样使用队列的,一般情况下出队的元素就不再有保存价值了,这些元素的存储空间应该回收利用,由此想到把队列改造成环形队列(Circular Queue):把queue数组想像成一个圈,front和rear指针仍然是一直增大的,当指到数组末尾时就自动回到数组开头,就像两个人围着操场赛跑,沿着它们跑的方向看,从front到rear之间是队列的有效元素,从rear到front之间是空的存储位置,如果front追上rear就表示队列空了,如果rear追上front就表示队列的存储空间满了。故一般我们将其实现为循环队列,当出队列时就不需要全部进行移动,只需要修改队头指针,也可以解决“假溢出”的问题。
数据结构:队列的顺序存储结构(循环队列)
示例程序:(改编自《大话数据结构》)

#include<iostream>
using namespace std;

#define MAXSIZE 20

typedef int ElemType;

typedef struct
{
ElemType data[MAXSIZE];
int front; /* 头指针 */
int rear; /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
int count; //元素个数
} SqQueue;

bool InitQueue(SqQueue &Sq)
{
cout << "Init Queue ..." << endl;
Sq.front = 0;
Sq.rear = 0;
Sq.count = 0;
return true;
}

bool ClearQueue(SqQueue &Sq)
{
cout << "Clear Queue ..." << endl;
Sq.front = 0;
Sq.rear = 0;
Sq.count = 0;
return true;
}

bool QueueEmpty(SqQueue &Sq)
{
return Sq.count == 0; /* 队列空的标志 */
}

bool QueueFull(SqQueue &Sq)
{
return Sq.count == MAXSIZE;
}

int QueueLength(SqQueue &Sq)
{
if (QueueFull(Sq))
return MAXSIZE;

/* 队列的当前长度 */
return (Sq.rear - Sq.front + MAXSIZE) % MAXSIZE;
}
/* 返回头元素 */
bool GetHead(SqQueue &Sq, ElemType *pe)
{
if (QueueEmpty(Sq))
return false;
else
{
*pe = Sq.data[Sq.front];
cout << "Get Head Item " << *pe << endl;
return true;
}
}

bool EnQueue(SqQueue &Sq, ElemType Elem)
{
/* 队列满 */
if (QueueLength(Sq) == MAXSIZE)
return false;
cout << "EnQueue Item " << Elem << endl;
Sq.data[Sq.rear] = Elem;/* 将元素赋值给队尾 */
Sq.rear = (Sq.rear + 1) % MAXSIZE;/* rear指针向后移一位置, */
/* 若到最后则转到数组头部 */
Sq.count++;
return true;
}

bool DeQueue(SqQueue &Sq, ElemType *pe)
{
if (QueueEmpty(Sq))
return false;
*pe = Sq.data[Sq.front];/* 将队头元素赋值给*pe */
cout << "DeQueue Item " << *pe << endl;
Sq.front = (Sq.front + 1) % MAXSIZE;/* front指针向后移一位置, */
/* 若到最后则转到数组头部 */

Sq.count--;
return true;
}

bool QueueTraverse(SqQueue &Sq)
{
if (QueueEmpty(Sq))
{
cout << "Queue is empty" << endl;
return false;
}

cout << "Queue Traverse ..." << endl;
for (int i = 0; i < Sq.count; i++)
cout << Sq.data[i + Sq.front] << ' ';
cout << endl;
return true;
}

int main(void)
{
SqQueue Sq;
InitQueue(Sq);
for (int i = 0; i < 20; i++)
EnQueue(Sq, i);
QueueTraverse(Sq);
if (!QueueEmpty(Sq))
cout << "Queue Length: " << QueueLength(Sq) << endl;
int result;
GetHead(Sq, &result);
DeQueue(Sq, &result);
DeQueue(Sq, &result);
if (!QueueEmpty(Sq))
cout << "Queue Length: " << QueueLength(Sq) << endl;
QueueTraverse(Sq);

return 0;
}

输出为:
数据结构:队列的顺序存储结构(循环队列)

单是顺序存储,若不是循环队列,算法的时间性能是不高的,但循环队列也面临着数组可能溢出的问题。
注:上述用 Use a fill count to distinguish the two cases. 的方法实现循环队列。常用的还有 Always keep one slot open. 也就是多申请一个不用的元素
位置,那么判断满时 (cb->end + 1) % cb->size == cb->start; 判断空时 cb->end == cb->start;

参考:
《大话数据结构》
《Data Structures》

转载自:http://blog.csdn.net/jnu_simba/article/details/8841657