基本數(shù)據(jù)結(jié)構(gòu)：隊(duì)列（queue）
作者：C小加 更新時(shí)間：2012-8-2
像棧一樣，隊(duì)列（queue）也是一種線性表，它的特性是先進(jìn)先出，插入在一端，刪除在另一端。就像排隊(duì)一樣，剛來的人入隊(duì)（push）要排在隊(duì)尾(rear)，每次出隊(duì)(pop)的都是隊(duì)首(front)的人。如圖1，描述了一個(gè)隊(duì)列模型。
和棧一樣，隊(duì)列也有數(shù)組實(shí)現(xiàn)和鏈表實(shí)現(xiàn)兩種，兩種實(shí)現(xiàn)都能給出快速的O(1)運(yùn)行時(shí)間，區(qū)別在于鏈表實(shí)現(xiàn)指針域要占用空間，頻繁的new和delete會(huì)消耗不少的時(shí)間開銷，數(shù)組實(shí)現(xiàn)唯一的缺點(diǎn)是建立時(shí)要確定空間大小。
假如一個(gè)隊(duì)列最多只能站10個(gè)人，當(dāng)占滿10個(gè)人后，第11個(gè)人就不能入隊(duì)，這種情況成為溢出。而如果第一個(gè)人出隊(duì)了，剩下的9個(gè)人依然還在原來的位置，隊(duì)列里空出了一個(gè)位置，但第11個(gè)人還是不能入隊(duì)，這種情況成為假溢出。克服假溢出有效的辦法是使用循環(huán)隊(duì)列。
循環(huán)隊(duì)列就是把隊(duì)尾和隊(duì)首連接起來，形成一個(gè)環(huán)，隊(duì)尾的下一個(gè)位置就是隊(duì)首，這樣可以有效的防止假溢出現(xiàn)象，但隊(duì)列的實(shí)際容量已然固定。
隊(duì)列的實(shí)現(xiàn)
隊(duì)列的數(shù)組實(shí)現(xiàn)和棧差不多，不同的是，棧用top做下標(biāo)，隊(duì)列用front和rear作為下標(biāo)。
我更改了單鏈表的模板來實(shí)現(xiàn)一個(gè)簡單的隊(duì)列。代碼僅供學(xué)習(xí)，不足之處還請(qǐng)指明，我會(huì)對(duì)不足之處進(jìn)行修改和更新。
代碼如下：
template<class T>
class queueNode
{
public:
queueNode():next(NULL){}
T data;//值
queueNode* next;//指向下一個(gè)節(jié)點(diǎn)的指針
};
template<class T>
class myqueue
{
private:
unsigned int queuelength;
queueNode<T>* node;//臨時(shí)節(jié)點(diǎn)
queueNode<T>* rear;//隊(duì)尾
queueNode<T>* front;//隊(duì)首
public:
myqueue();//初始化
unsigned int length();//隊(duì)列元素的個(gè)數(shù)
void push(T x);//入隊(duì)
bool isEmpty();//判斷隊(duì)列是否為空
void pop();//出隊(duì)
T getHead();//獲得隊(duì)首元素
};
template<class T>
myqueue<T>::myqueue()
{
node=NULL;
rear=NULL;
front=NULL;
queuelength=0;
}
template<class T>
inline unsigned int myqueue<T>::length(){return queuelength;}
template<class T>
void myqueue<T>::push(T x)
{
node=new queueNode<T>();//申請(qǐng)一個(gè)新的節(jié)點(diǎn)
node->data=x;//新節(jié)點(diǎn)賦值為x
if(rear==NULL)//如果沒有尾節(jié)點(diǎn)則隊(duì)列為空,node既為隊(duì)首,又是隊(duì)尾
{
front=node;
rear=node;
}
else//如果隊(duì)列非空
{
rear->next=node;//node既為尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
rear=node;//node變成了尾節(jié)點(diǎn),把尾節(jié)點(diǎn)賦值為node
}
++queuelength;//元素個(gè)數(shù)+1
}
template<class T>
bool myqueue<T>::isEmpty()
{
return queuelength==0;
}
template<class T>
void myqueue<T>::pop()
{
if(queuelength==0) return;
node=front;
front=front->next;
delete(node);
--queuelength;
}
template<class T>
T myqueue<T>::getHead()
{
return front->data;
}
隊(duì)列的應(yīng)用
打印機(jī)處理作業(yè)采用的就是隊(duì)列結(jié)構(gòu)，它們會(huì)按照提交的順序排列起來。STL也給出了一個(gè)強(qiáng)大的隊(duì)列，我們直接可以去用它。
隊(duì)列相關(guān)問題
如何用兩個(gè)棧模擬一個(gè)隊(duì)列，如果用兩個(gè)隊(duì)列模擬一個(gè)棧？