数据结构的C++实现之队列的顺序存储结构（循环队列）

数据结构的C++实现之队列的顺序存储结构（循环队列）2013-08-13 csdn Simba888888队列（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 20typedef int ElemType;typedef struct{ElemType data[MAXSIZE];int front; /* 头指针 */int rear; /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */} SqQueue;bool InitQueue（SqQueue *pq）{cout << "Init Queue ..." << endl;pq->front = 0;pq->rear = 0;return true;}bool ClearQueue（SqQueue *pq）{cout << "Clear Queue ..." << endl;pq->front = 0;pq->rear = 0;return true;}bool QueueEmpty（SqQueue Sq）{return （Sq.front == Sq.rear）; /* 队列空的标志 */}int QueueLength（SqQueue Sq）{/* 队列的当前长度 */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 *pq, ElemType Elem）{ /* 队列满 */if （QueueLength（*pq） == MAXSIZE）return false;cout << "EnQueue Item " << Elem << endl;pq->data[pq->rear] = Elem;/* 将元素赋值给队尾 */pq->rear = （pq->rear + 1） % MAXSIZE;/* rear指针向后移一位置， *//* 若到最后则转到数组头部 */return true;}bool DeQueue（SqQueue *pq, ElemType *pe）{if （QueueEmpty（*pq））return false;*pe = pq->data[pq->front];/* 将队头元素赋值给*pe */cout << "DeQueue Item " << *pe << endl;pq->front = （pq->front + 1） % MAXSIZE;/* front指针向后移一位置， *//* 若到最后则转到数组头部 */return true;}bool QueueTraverse（SqQueue Sq）{cout << "Queue Traverse ..." << endl;for （int i = 0; Sq.front + i < Sq.rear; i = （i + 1） % MAXSIZE）cout << Sq.data[i + Sq.front] << " ";cout << endl;return true;}int main（void）{SqQueue Sq;InitQueue（&Sq）;for （int i = 0; i < 5; i++）EnQueue（&Sq, i）;QueueTraverse（Sq）;int result;GetHead（Sq, &result）;DeQueue（&Sq, &result）;DeQueue（&Sq, &result）;if （！QueueEmpty（Sq））cout << "Queue Length: " << QueueLength（Sq） << endl;QueueTraverse（Sq）;return 0;}

输出为：

单是顺序存储，若不是循环队列，算法的时间性能是不高的，但循环队列也面临着数组可能溢出的问题。