什么是隊列結構
隊列結構是從數據運算來分類的，也就是說隊列結構具有特殊的運算規則。而從數據的邏輯結構來看，隊列結構其實就是一種線性結構。如果從數據的存儲結構來進一步劃分，隊列結構可以分成兩類。
順序隊列結構：即使用一組地址連續的內存單元依次保存隊列中的數據。在程序中，可以定義一個指定大小的結構數組來作為隊列。
鏈式隊列結構：即使用鏈表形式保存隊列中各元素的值。
在隊列結構中允許對兩端進行操作，但是兩端的操作不同。在表的一端只能進行刪除操作，稱為隊頭；在表的另一端只能進行插入操作，稱為隊尾。如果隊列中沒有數據元素，則稱之為空隊列。從數據的運算角度分析，隊列是按照“先進先出”的原則處理結點的。
可以將隊列結構理解成是：超市排隊結賬的人群，排在隊首的人先結賬，然后不斷會有人排在隊尾等待結賬，這就是一個先來先服務的隊列的現實中的例子。
一般隊列結構的基本操作只有兩個：
入隊列：將一個元素添加到隊尾（相當于到隊列最后排隊等待）
出隊列：將對頭的元素取出，同時刪除該元素，使后一個元素成為隊頭。
初次之外，還有初始化隊列、獲取隊列長度的簡單運算。下面，我們就是用C++建立順序隊列結構，并完成順序隊列結構的基本運算。
準備數據
準備數據就是定義在隊列操作中需要用到的變量及數據結構等。
struct DATA{
string name;
int age;
};
struct SQType
{
DATA data[QUEUELEN]; //隊列數組
int head; //隊頭
int tail; //隊尾
};
這里，定義了隊列結構的最大長度QUEUELEN ,隊列結構數據元素的類型DATA以及隊列結構的數據結構SQType。在數據結構SQType中，data為數據元素，head為隊首的序號，tail為隊尾的序號。當head=0時表示隊列為空，當tail=QUEUELEN時表示隊列滿。初始化隊列數據
順序隊列的初始化操作步驟如下：
（1）按符號常量QUEUELEN指定的大小申請一段內存空間，用來保存隊列中的數據。
（2）設置head=0和tail=0，表示一個空棧。
示例代碼如下：
SQType *SQTypeInit()
{
SQType * q;
if(q=new SQType) //申請隊列的內存空間
{
q->head=0; //設置隊首
q->tail=0; //設置隊尾
return q;
}
else
{
return NULL; //返回空
}
}
首先使用new申請內存，申請成功以后設置隊頭和隊尾，然后返回申請內存的首地址，如果申請失敗則返回NULL。判斷空隊列
判斷空隊列是判斷一個隊列結構是否為空。如果是空隊列，則表示該隊列結構中國沒有數據。此時可以進入如隊列操作，不可以進行出隊列操作。
示例代碼如下：
int SQTypeIsEmpty(SQType *q)
{
return(q->head==q->tail);
}
輸入參數q為一個指向操作的隊列的指針。程序中，根據隊列head是否等于tail判斷隊列是否為空。判斷滿隊列
判斷滿隊列就是判斷一個隊列結構是否為滿。如果是滿隊列，則表示該隊列中沒有多余的空間來保存額外數據。測試不可以進行入隊列操作，可以進行出隊列操作。
示例代碼如下：
int SQTypeIsFull(SQType *q)
{
return(q->tail==QUEUELEN)
}
輸入參數q為一個指向操作的隊列的指針。程序中，根據隊列tail是否等于隊列的最大值QUEUELEN判斷隊列是否是滿的。清空隊列
清空隊列就是清楚一個隊列中的所有的數據。示例代碼如下：
void SQTypeClear(SQType *q)
{
q->head=0;
q->tail=0;
}
將隊列頂指針head和尾指針tail設置為0，表示執行清空操作。釋放空間
釋放空間是釋放隊列結構所占用的內存單元。由前面可知，在初始化隊列結構時，使用了new關鍵字分配內存單元。雖然可以使用清空隊列操作，但是清空隊列操作并沒有釋放內存空間，這就需要使用delete關鍵字釋放所占的內存單元。
示例代碼如下：
void SQTypeFree(SQType *q)
{
if(q!=NULL) delete q;
}
程序中，調用了得delete釋放new申請的內存空間。入隊列
入隊列是隊列結構的基本操作，主要操作是將數據元素保存到隊列結構。入隊列操作的具體步驟如下：
（1）首先判斷隊尾，如果tail等于QUEUELEN，則表示溢出，進行出錯處理。否則執行以下操作。
（2）設置tail=tail+1（隊列頂指針加1，指向入隊列地址）
（3）就將入隊列元素保存到tail指向的位置
示例代碼如下：
int InSQType(SQType *q,DATA data)
{
if(q->tail==QUEUELEN)
{
cout<<"隊列已滿！操作失?。?<<endl;
return 0;
}else
{
q-data[q->tail++]=data; //將元素入隊列
return 1;
}
}
輸入參數q為指向操作的隊列的指針，輸入參數data為需要入隊列的數據元素。程序中首先判斷隊列是否溢出，如果溢出則不進行入隊列操作，否則修改隊列頂指針的值，再將元素入隊列。因為tail的值從0開始，當前的值就是要插入的數組對應的元素的位置，所以寫成q->tail++。
出隊列
出隊列是隊列結構的基本操作，主要操作與入隊列相反，其實從隊列頂彈出一個數據元素。出隊列操作的具體步驟如下：
（1）首先判斷隊首head，如果head等于tail，則表示為空隊列，進行出錯處理。否則，執行下面的步驟
（2）從隊列首部取出隊頭元素（實際返回隊頭元素的指針）
（3）修改隊首head的序號，使其指向后一個元素。
示例代碼如下：
DATA *OutSQType(SQType *q)
{
if(q->tail==q->head)
{
cout<<"隊列已空！操作失??！"<<endl;
exit(0);
}else
{
return &(q->data[q->head++]);
}
}
輸入參數q為指向操作的隊列的指針。該函數返回值是一個DATA類型的數據，返回值是指向該數據元素的指針。
讀結點數據讀結點數據也就是讀取隊列結構中結點的數據，這里的讀操作其實就是讀隊列頭的數據。需要助于的是，讀結點數據的操作和出隊列操作不同。讀結點數據的操作僅是顯示隊列頂結點數據的內容，而出隊列操作則將隊列頂數據彈出，該數據不再存在。
示例代碼如下：
DATA * PeekSQType(SQType *q)
{
if(SQTypeIsEmpty(q))
{
cout<<"空隊列"<<endl;
return NULL;
}else
{
return &(q->data[q->head]);
}
}
該函數返回值同樣是一個DATA類型的指針數據，返回值是指向數據元素的指針。
計算隊列長度計算隊列長度就是統計該隊列中數據結點的個數。計算隊列長度的方法比較簡單，直接隊尾序號減去隊首序號即可。
示例代碼如下：
int SQTypeLen(SQType *q)
{
return(q->tail-q->head);
}
隊列結構操作實例代碼：完整的代碼會比較長，不過函數部分和上面介紹的基本一致，主要是看main函數中這些函數的用法：
#include<iostream>
#include<string>
using namespace std;
#define QUEUELEN 10
struct DATA{
string name;
int age;
};
struct SQType
{
DATA data[QUEUELEN]; //隊列數組
int head; //隊頭
int tail; //隊尾
};
/*******************隊列的初始化*************************/
SQType *SQTypeInit()
{
SQType * q;
if(q=new SQType) //申請隊列的內存空間
{
q->head=0; //設置隊首
q->tail=0; //設置隊尾
return q;
}
else
{
return NULL; //返回空
}
}
/*******************判斷空隊列*************************/
int SQTypeIsEmpty(SQType *q)
{
return(q->head==q->tail);
}
/*******************判斷滿隊列*************************/
int SQTypeIsFull(SQType *q)
{
return(q->tail==QUEUELEN);
}
/*******************清空隊列*************************/
void SQTypeClear(SQType *q)
{
q->head=0;
q->tail=0;
}
/*******************釋放空間*************************/
void SQTypeFree(SQType *q)
{
if(q!=NULL) delete q;
}
/*******************入隊列操作*************************/
int InSQType(SQType *q,DATA data)
{
if(q->tail==QUEUELEN)
{
cout<<"隊列已滿！操作失??！"<<endl;
return 0;
}else
{
q->data[q->tail++]=data; //將元素入隊列
return 1;
}
}
/*******************出隊列操作*************************/
DATA *OutSQType(SQType *q)
{
if(q->tail==q->head)
{
return NULL;
}else
{
return &(q->data[q->head++]);
}
}
/*******************讀結點數據*************************/
DATA * PeekSQType(SQType *q)
{
if(SQTypeIsEmpty(q))
{
cout<<"空隊列"<<endl;
return NULL;
}else
{
return &(q->data[q->head]);
}
}
/*******************計算隊列長度*************************/
int SQTypeLen(SQType *q)
{
return(q->tail-q->head);
}
/*********************主函數******************************/
int main()
{
SQType *stack;
DATA data,*p;
stack=SQTypeInit(); //執行初始化操作
cout<<"執行入隊列操作："<<endl;
cout<<"輸入姓名,年齡進行入隊操作："<<endl;
while(1)
{
cin>>data.name>>data.age;
if(data.age==0)
{
break; //若輸入為0，則退出
}
else
{
InSQType(stack,data);
}
}
cout<<"進行出棧操作："<<endl;
p=OutSQType(stack);
cout<<p->name<<","<<p->age<<endl;
cout<<"讀取首結點數據："<<endl;
p=PeekSQType(stack);
cout<<p->name<<","<<p->age<<endl;
cout<<"執行出棧操作："<<endl;
while(1)
{
if(SQTypeIsEmpty(stack))
{
cout<<"所有數據出棧完畢，棧為空！"<<endl;
break;
}else
{
p=OutSQType(stack);
cout<<p->name<<","<<p->age<<endl;
}
}
SQTypeFree(stack);
return 0;
}
程序運行界面：
