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

队列（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; /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
} 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;
}

输出为：

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

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索指针
， 数组
， 循环队列
， 存储
， 队列
， return
， maxsize
， 元素
， 循环队列存储
， c++顺序栈
， 顺序队列
， 环形队列类
， 环形队列
环形无锁队列
顺序循环队列的实现、循环队列的实现、设顺序循环队列、设顺序循环队列q、顺序循环队列，以便于您获取更多的相关知识。