這篇部落格參考嚴蔚敏老師《資料結構》第二版
之前的部落格講到了棧，它是一種線上性表上的操作受限的資料結構。這次我們來看另一種線上性表上的操作受限的資料結構—隊列。
注意：隊列無法進行查找
前言
和棧相反，隊列是一種先進先出的線性表，它隻允許在表的一端進行插入操作，在一端進行删除操作。進行删除的一端我們成為隊頭，進行插入的一端我們稱為隊尾。
鑒于大家容易搞混哪是隊首，哪是隊尾。大家不妨聯系自己排隊的時候就很明哪是隊尾和隊首了。
接下來，我們看看隊列有哪些基本操作。
各種操作
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;
好了，這次的部落格就到這了。