顺序队列（循环队列）

1.队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
2.队列是一种先进先出（First In Fist Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。

队列
Q1:假设长度为5的队列中此时情况如下： 问题
即入队时已经越界，而前面还有诸多空间未利用，故使用循环队列，入队元素存入未利用的空间，即下图所示
解决
Q2:我们发现队空时，front==end,队满时也是front==end,如下图所示：
问题
解决办法1：设置标志量flag，
解决办法2：保留一个元素空间，即使得队列中最多存储MAXSIZE-1个元素，这样，队满条件变为(rear+1)%MAXSIZE==front,与队空条件不会冲突，如下图所示
解决
queue.h

#pragma once

#define MAXSIZE 10
// 函数结果状态代码
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2

//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;

//数据类型
typedef int QElemType;

//顺序队列定义
typedef struct
{
    QElemType* base;    //初始化的动态分配存储空间
    int front;          //头指针
    int rear;           //尾指针
}SqQueue;

//初始化队列
Status InitSqQueue(SqQueue& Q);

//求队列长度
int QueueLength(SqQueue Q);

//入队
Status EnQueue(SqQueue& Q, QElemType e);

//出队
Status DeQueue(SqQueue& Q, QElemType& e);

//取队头元素
QElemType GetHead(SqQueue Q);

queue.cpp

#include "queue.h"
#include <iostream>
using namespace std;

//初始化队列
Status InitSqQueue(SqQueue& Q)
{
    Q.base = new QElemType[MAXSIZE];

    if (!Q.base)
    {
        exit(OVERFLOW);
    }
    Q.front = Q.rear = 0;
}

//求队列长度
int QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

//入队
Status EnQueue(SqQueue& Q, QElemType e)
{
    if ((Q.rear + 1) % MAXSIZE == Q.front)
    {
        cout << "队满" << endl;
        return ERROR;
    }

    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
}

//出队
Status DeQueue(SqQueue& Q, QElemType& e)
{
    if (Q.front == Q.rear)
    {
        cout << "队空" << endl;
        return ERROR;
    }

    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
}

//取队头元素
QElemType GetHead(SqQueue Q)
{
    if (Q.front == Q.rear)
    {
        cout << "队空" << endl;
        return ERROR;
    }

    return Q.base[Q.front];
}

main.cpp

#include <iostream>
#include "queue.h"
using namespace std;

int main(int argc, char** argv)
{
    SqQueue Q;
    InitSqQueue(Q);

    for (int i = 0; i < MAXSIZE + 1; i++)       //MAXSIZE为10，只能存9个，会有队满情况发生
    {
        EnQueue(Q, i);
    }

    QElemType h = GetHead(Q);
    cout << "队头元素:" << h << endl;

    int length = QueueLength(Q);
    cout << "队列长度:" << length << endl;

    QElemType x;
    for (int i = 0; i < MAXSIZE + 2; i++)       //存了9个，会有队空情况发生
    {
        DeQueue(Q, x);
        cout << x << endl;
    }

    return 0;
}