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