这篇博客参考严蔚敏老师《数据结构》第二版
之前的博客讲到了栈，它是一种在线性表上的操作受限的数据结构。这次我们来看另一种在线性表上的操作受限的数据结构—队列。
注意：队列无法进行查找
前言
和栈相反，队列是一种先进先出的线性表，它只允许在表的一端进行插入操作，在一端进行删除操作。进行删除的一端我们成为队头，进行插入的一端我们称为队尾。
鉴于大家容易搞混哪是队首，哪是队尾。大家不妨联系自己排队的时候就很明哪是队尾和队首了。
接下来，我们看看队列有哪些基本操作。
各种操作
1，队列的声明
由于队列是特殊的线性表，我们在进行顺序存储时，可以使用高级语言的数组来进行数据存储，由于队列需要进行的有入队和出队，且都是在两端进行，因此我们在结构中还要定义队尾和队首指针。
不过在之前，我们先看一张图片：
我们在怎样有效的利用已经出队过的空间呢？
答案是我们将首尾相连即可！构成一个环！
博主在学习的时候也是惊呆了，计算机内部还有环这种操作？那咋实现呢？
在之后的学习中我也渐渐了解，原来计算机内部没有环，只是逻辑上而已，物理内存还是一个一维的连续空间！
来看图片：
这样队头指针不断出队，队尾指针不断入队。以前使用过的空间还可以使用！
但是这只是逻辑上的，物理其实大概类似与这张图片：
我们通过取模运算，来达到目的，
比如:
“假溢出”的队列
入队：rear++
出队：front++
“循环队列”：
入队：rear=(rear+1)%MAXSIZE
出队：front=(front+1)%MAXSIZE
那循环队列操作不是更复杂吗？
虽然是这样，但循环队列的作用很大，比如某些地方循环队列有奇效，随着我们接下来的学习就知道了，其实这个数据结构还是没有和非线性的数据结构复杂呀！
那现在还有问题：我们现在如何判断循环队列是满的状态？
这里博主由于能力有限就直接给出答案了。
我们一般有两种方式来判断循环队列是否是满的状态
1，少用一个元素空间，即队列空间大小为m时，有m-1个元素就已经满了
2，另设一个标志位来区别队列是否满了。
我们这篇博客主要以第一种方式，第二种方式博主以后给出。
现在是少用一个元素空间，来判断循环队列是否已经满了。
即：
队空：front==rear
队满：(rear+1)%MAXSIZE=front
我们来看代码：
typedef struct {
QElemType *base;
int front; //头指针
int rear; //尾指针
}SqQueue;
2，队列的初始化
算法思想：为队列分配一个最大容量MAXSIZE，头指针和尾指针都置为0，表示队列为空
Status InitQueue(SqQueue& Q)//队列的初始化
{
Q.base=new QElemType[MAXSIZE]; // 分配空间
Q.front=Q.rear=0; //队列为空
return OK;
}
3，求队列的长度
算法思想：
我们先进行一波分析
（1）：当front<rear时，这很容易看出队列的长度
即： rear - front
（2）：当front>rear时，
来看图片：
我们可以用公式：
(rear-front+MAXSIZE)%MAXSIZE得到队列的长度。
来看代码：
int QueueLength(SqQueue& Q)//求队列的长度
{
return (MAXSIZE+Q.rear-Q.front)%MAXSIZE; //求的循环队列的长度
}
4，入队
算法步骤：
（1）判断队列是否已满，若满了则无法插入，返回ERROR
（2）将新元素插入队尾，队尾指针加1
来看代码：
Status EnQueue(SqQueue& Q,QElemType e)//入队
{
if((Q.rear+1)%MAXSIZE==Q.front)//队满了，无法进行插入
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return OK;
}
5，出队
算法步骤：
（1）判断队列是否为空，若队列为空，则无法删除元素，返回ERROR
（2）保存队头元素，对头指针加1
来看代码：
Status DeQueue(SqQueue& Q,QElemType e)//出队
{
if(Q.front==Q.rear) //队为空
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE; //队头指针加一
return OK;
}
6，取循环队列的队头元素
算法思想：
若当前队列不为空时，我们返回队头的元素，队头指针不变
来看代码：
QElemType GetHead(SqQueue& Q)//取队头元素
{
if(Q.front!=Q.rear) //队列非空
return Q.base[Q.front];
}
下面给出完整源码：
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define Status int
#define MAXSIZE 100 //队列的最大长度
typedef int QElemType ;
typedef struct {
QElemType *base;
int front; //头指针
int rear; //尾指针
}SqQueue;
Status InitQueue(SqQueue& Q);//队列的初始化
int QueueLength(SqQueue& Q) ;//求队列的长度
Status EnQueue(SqQueue& Q,QElemType e);//入队
Status DeQueue(SqQueue& Q,QElemType e);//出队
QElemType GetHead(SqQueue& Q);//取队头元素
int main(){
return 0;
}
Status InitQueue(SqQueue& Q)//队列的初始化
{
Q.base=new QElemType[MAXSIZE]; // 分配空间
Q.front=Q.rear=0; //队列为空
return OK;
}
int QueueLength(SqQueue& Q)//求队列的长度
{
return (MAXSIZE+Q.rear-Q.front)%MAXSIZE; //求的循环队列的长度
}
Status EnQueue(SqQueue& Q,QElemType e)//入队
{
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)//出队
{
if(Q.front==Q.rear) //队为空
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE; //队头指针加一
return OK;
}
QElemType GetHead(SqQueue& Q)//取队头元素
{
if(Q.front!=Q.rear)//队列非空
return Q.base[Q.front];
}
/*
* 由于队列可以采用顺序表来进行顺序存储
* 但会出现一下问题： 1，真溢出。 2，假溢出
* 我们需要对队列进行改变----->循环队列
*
*/
/* 队尾插入-> rear, 队头删除-> front */
/* 队头指针和队尾指针都是要进行前移*/
/*
* 我们采用牺牲一个空间来判断队满 和队空的情况
* 队空： Q.front==Q.rear
* 队满： (Q.rear+1)%MAXSIZE=Q.front
* 队头指针前移： Q.front=(Q.front+1)%MAXSIZE
* 队尾指针前移： Q.rear=(Q.rear+1)%MAXSIZE
*
*/
下面给出测试代码：
SqQueue Q;//这是一个队列
int value=0;
InitQueue(Q); //初始化
cout<<"请输入你想要输入队列的数字：";
cin>>value;
if(EnQueue(Q,value)){
cout<<value<<"成功入队了！"<<endl;
}else{
cout<<value<<"失败入队了！"<<endl;
}
int num=QueueLength(Q); //获得队列的长度
cout<<"现在队列有"<<num<<"个数！"<<endl;
cout<<"请输入你想要输入队列的数字：";
cin>>value;
if(EnQueue(Q,value)){
cout<<value<<"成功入队了！"<<endl;
}else{
cout<<value<<"失败入队了！"<<endl;
}
num=QueueLength(Q); //获得队列的长度
cout<<"现在队列有"<<num<<"个数！"<<endl;
cout<<"现在将进行出队操作"<<endl;
if(DeQueue(Q,value)){
cout<<"删除成功了！"<<endl;
}else{
cout<<"删除失败了！"<<endl;
}
num=QueueLength(Q); //获得队列的长度
cout<<"现在队列有"<<num<<"个数！"<<endl;
好了，这次的博客就到这了。