循环队列的顺序存储实现（入队，出队，清队，销毁队，遍历等）

循环队列的顺序存储实现，包括入队，出队，清队，销毁队，遍历队列等

队列（queue）是一种先进先出（first in fist out，缩写为FIFO）的线性表，它只允许在表的一端进行插入，而在另一端进行删除元素。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。

具体的代码实现如下

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

#define MAXSIZE     100
#define OVERFLOW    -2
#define OK          1
#define TRUE        1
#define FALSE       0
#define ERROR       1

typedef int QElemType;
typedef int Status;
///循环队列的顺序存储方式
struct SqQueue
{
    QElemType *base;
    int front;
    int rear;
};

Status InitQueue(SqQueue &Q);///构造一个空队列
Status DestroyQueue(SqQueue &Q);///销毁队列Q，Q不再存在
Status ClearQueue(SqQueue &Q);///将Q清为空队列
Status QueueEmpty(SqQueue Q);///若队列Q为空，则返回TRUE，否则返回FALSE
int QueueLength(SqQueue Q);///返回Q的元素个数，即为队列的长度
Status GetHead(SqQueue Q, QElemType &e);///若队列不为空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
Status EnQueue(SqQueue &Q, QElemType e);///插入元素e为Q的新的队尾元素
Status DeQueue(SqQueue &Q, QElemType &e);///若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
void visit(QElemType e);///输出元素e
Status QueueTraverse(SqQueue Q, void(*visit)(QElemType));///遍历队列Q


Status InitQueue(SqQueue &Q)
{
    ///构造一个空队列Q
    Q.base = (QElemType *)malloc(MAXSIZE * sizeof(QElemType));
    if(!Q.base)
        exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

Status DestroyQueue(SqQueue &Q){
    ///销毁队列Q，Q不再存在
    if(Q.base)
        free(Q.base);
    Q.base = NULL;
    Q.front = Q.rear = 0;
    return OK;
}

Status ClearQueue(SqQueue &Q){
    ///将Q清为空队列
    Q.front = Q.rear = 0;
    return OK;
}

Status QueueEmpty(SqQueue Q){
    ///判断队列是否为空
    if(Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}

int QueueLength(SqQueue Q)
{
    ///返回Q的元素个数，即队列的长度
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

Status GetHead(SqQueue Q, QElemType &e){
    ///若队列不为空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
    if(Q.front == Q.rear)
        return ERROR;
    e = Q.base[Q.front];
    return OK;
}

Status EnQueue(SqQueue &Q, QElemType e)
{
    ///插入元素e，为Q的新的队尾元素
    if((Q.rear + 1) % MAXSIZE == Q.front) ///队列满
        return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}

Status DeQueue(SqQueue &Q, QElemType &e)
{
    ///若队列不空，则删除Q的队头元素，用e返回其值，并返回OK;否则返回ERROR
    if(Q.front == Q.rear)
        return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return OK;
}

void visit(QElemType e){
    ///输出元素e
    cout << e << " ";
}
Status QueueTraverse(SqQueue Q, void(*visit)(QElemType)){
    ///利用指针函数，遍历队列Q
    int i;
    i = Q.front;
    while(i != Q.rear){
        visit(Q.base[i]);
        i = (i + 1) % MAXSIZE;
    }
    cout << endl;
    return OK;
}

int main()
{
    int i = 0,l;
    Status j;
    QElemType e;
    SqQueue Q;
    InitQueue(Q);
    if(!QueueEmpty(Q))
        cout << "队列为空。" << endl;
    cout << "请输入值到队列中，长度应小于" << MAXSIZE -1 << endl;
    do{
        cin >> e;
        ++i;
        if(e == -1){
            break;
        }
        EnQueue(Q,e);
    }while(i < MAXSIZE -1);

    cout << "队列的长度为：" << QueueLength(Q) << endl;
    cout << "开始从队头删除元素，从队尾插入元素:" << endl;
    for(i = 0; i < QueueLength(Q); ++i){
        DeQueue(Q,e);
        cout << "删除的元素为：" << e << ".请输入新的值进行插入：";
        cin >> e;
        EnQueue(Q,e);
    }
    l = QueueLength(Q);
    cout << "队列的元素为：" << endl;
    QueueTraverse(Q,visit);
    j = GetHead(Q,e);
    cout << "队列的首元素为：" << e << endl;
    ClearQueue(Q);
    if(!QueueEmpty(Q))
        cout << "队列不为空！" << endl;
    else
        cout << "队列为空！" << endl;
    DestroyQueue(Q);
    return 0;
}

运行结果如下：

在这里插入图片描述

循环队列的顺序存储实现（入队，出队，清队，销毁队，遍历等）

循环队列的顺序存储实现，包括入队，出队，清队，销毁队，遍历队列等

队列（queue）是一种先进先出（first in fist out，缩写为FIFO）的线性表，它只允许在表的一端进行插入，而在另一端进行删除元素。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。

运行结果如下：

队列不宜像栈那样，进行存储在分配数组空间，因为队列的实际可用空间并未沾满。

浏览过的版块