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