本文更新于個(gè)人博客Burnside Blog
在數(shù)據(jù)結(jié)構(gòu)中，最重要且最基礎(chǔ)的兩項(xiàng)就是棧與隊(duì)列。一提到隊(duì)列（Queue），相信大家都不陌生，它不像棧這個(gè)名字一樣抽象，而是是一種很形象的結(jié)構(gòu)，因?yàn)樗旧砭涂梢岳斫獬梢粋€(gè)隊(duì)列。考慮我們排一路縱隊(duì)在某個(gè)窗口辦事，辦完事的人一定是從隊(duì)首離開隊(duì)列，而想要進(jìn)來辦事的人一定是在隊(duì)尾入隊(duì)（假設(shè)一隊(duì)人均素質(zhì)優(yōu)良，沒有插隊(duì)現(xiàn)象）。隊(duì)列也是如此，它是一種先入先出的數(shù)據(jù)結(jié)構(gòu)。
為了方便起見，我們不使用動(dòng)態(tài)方式生成一個(gè)隊(duì)列，或銷毀一個(gè)隊(duì)列，我們只考慮一個(gè)靜態(tài)的隊(duì)列的功能實(shí)現(xiàn)。隊(duì)列中的元素可以是任何的用戶自定義類型，為了方便起見，我們假設(shè)元素的類型為int，如需要?jiǎng)e的類型，只需要靈活處理即可。接下來我們申請(qǐng)一塊長(zhǎng)度為MaxSize的連續(xù)內(nèi)存來存儲(chǔ)這個(gè)隊(duì)列，這時(shí)它又被稱為順序隊(duì)。
int Queue[MaxSize];
這樣我們就獲得了一個(gè)最多能存儲(chǔ)MaxSize個(gè)元素的隊(duì)列，在隊(duì)列中，我們稱隊(duì)首為front，隊(duì)尾為rear，接下來我們只需要模擬整個(gè)入隊(duì)出隊(duì)的過程即可。
int enQueue(int x){
? ? Queue[++rear]=x;
? ? return rear;
}
int deQueue(){
? ? return ++front;
}
不難理解，和棧類似，隊(duì)列在入隊(duì)操作發(fā)生時(shí)也只是將隊(duì)尾的元素賦成新值，出隊(duì)時(shí)將隊(duì)首前移，這里要注意，隊(duì)首和隊(duì)尾在數(shù)組中存儲(chǔ)的邏輯正好是反著的，也就是隊(duì)尾的數(shù)組下標(biāo)要比隊(duì)首大，當(dāng)然，如果一個(gè)隊(duì)列為空，則隊(duì)尾和隊(duì)首的下標(biāo)相同。
這樣我們也可以寫一個(gè)函數(shù)來判斷一個(gè)隊(duì)列是否為空。
int empty(){
? ? return front==rear;
}
這就是隊(duì)列最簡(jiǎn)單的實(shí)現(xiàn)方式。但注意一點(diǎn)，為什么我們一開始說這個(gè)隊(duì)列最多只能存儲(chǔ)MaxSize個(gè)元素呢？因?yàn)槲覀儼l(fā)現(xiàn)，這個(gè)數(shù)組在不斷入隊(duì)出隊(duì)的過程中，實(shí)際上用到的空間只有隊(duì)首到隊(duì)尾的這一點(diǎn)空間，而我們申請(qǐng)下來的MaxSize的空間很多是被浪費(fèi)掉了的，再者，這個(gè)隊(duì)列最多只允許我們進(jìn)行MaxSize-1次的入隊(duì)和MaxSize-1次的合法出隊(duì)操作，因?yàn)樵谶M(jìn)行完這些操作后，隊(duì)首和隊(duì)尾的值就都等于MaxSize了，如果再進(jìn)行入隊(duì)出隊(duì)就要訪問到非法內(nèi)存了。
難道隊(duì)列就是一種如此低效的數(shù)據(jù)結(jié)構(gòu)嗎？并不是這樣的，因?yàn)槲覀儼l(fā)明了一種循環(huán)隊(duì)列，這種隊(duì)列有一個(gè)特性，就是如果我的隊(duì)尾或隊(duì)首已經(jīng)到MaxSize而我們想繼續(xù)操作的時(shí)候，下一次的入隊(duì)或合法的出隊(duì)操作會(huì)使得隊(duì)首或隊(duì)尾回到數(shù)組下標(biāo)為0的位置，將申請(qǐng)到的空間循環(huán)利用起來，具體實(shí)現(xiàn)如下。
入隊(duì)
bool enQueue(int x){
? ? if((rear+1)%MaxSize==front) return false;
? ? Queue[rear=(rear+1)%MaxSize]=x;
? ? return true;
}
因?yàn)檠h(huán)隊(duì)列特殊的性質(zhì)，也就是它的數(shù)組下標(biāo)是循環(huán)出現(xiàn)的，我們很容易想到用取余（Mod）來實(shí)現(xiàn)數(shù)組下標(biāo)的變換，在此函數(shù)中，返回值代表了入隊(duì)是否成功。
出隊(duì)
bool deQueue(){
? ? if(rear==front) return false;
? ? front=(front+1)%MaxSize;
? ? return true;
}
與入隊(duì)相似。
取隊(duì)首元素
int QueueFront(){
? ? return Queue[front];
}
此函數(shù)的功能是調(diào)用隊(duì)首的元素，書中好像把它和出隊(duì)操作寫在一起了，我不是很推薦這樣做，因?yàn)檎{(diào)用隊(duì)首的元素不一定要讓其出隊(duì)。
判斷隊(duì)列是否為空
bool Empty(){
? ? return front==rear;
}
和普通隊(duì)列一樣判斷就可以了。
經(jīng)過這樣的操作，我們就可以得到一個(gè)空間利用更高效的隊(duì)列。當(dāng)然，還有一種隊(duì)列叫雙端隊(duì)列（Deque），是支持隊(duì)首進(jìn)隊(duì)出隊(duì)、隊(duì)尾進(jìn)隊(duì)出隊(duì)的特殊隊(duì)列，寫法和循環(huán)隊(duì)列類似，讀者可以在閑暇時(shí)間獨(dú)立完成，書中貌似也有相關(guān)的代碼。
書中還介紹了隊(duì)列的鏈?zhǔn)酱鎯?chǔ)，也就是鏈隊(duì)，實(shí)現(xiàn)方式和順序隊(duì)類似，不再贅述。此外，還有隊(duì)內(nèi)元素保持單調(diào)性的單調(diào)隊(duì)列，常用于對(duì)動(dòng)態(tài)規(guī)劃問題（Dynamic Programming，DP）的優(yōu)化，常用于競(jìng)賽，感興趣可以自行了解。
此外，可能會(huì)有部分讀者表示我在實(shí)現(xiàn)普通隊(duì)列的時(shí)候，沒有考慮隊(duì)列的非法操作（隊(duì)滿時(shí)入隊(duì)，隊(duì)空時(shí)出隊(duì)），是因?yàn)槟欠N隊(duì)列的實(shí)現(xiàn)形式現(xiàn)在已經(jīng)不用了（因?yàn)橛懈玫难h(huán)隊(duì)列可以使用），因此沒有詳細(xì)處理細(xì)節(jié)，若想判斷的話只需要在兩個(gè)函數(shù)里分別加入if語(yǔ)句判斷即可。
