前面一篇博客我們講解了并不像數(shù)組一樣完全作為存儲(chǔ)數(shù)據(jù)功能恍风，而是作為構(gòu)思算法的輔助工具的數(shù)據(jù)結(jié)構(gòu)——棧蹦狂，本篇博客我們介紹另外一個(gè)這樣的工具——隊(duì)列誓篱。棧是后進(jìn)先出，而隊(duì)列剛好相反凯楔，是先進(jìn)先出窜骄。
1、隊(duì)列的基本概念
隊(duì)列（queue）是一種特殊的線性表摆屯，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作邻遏，而在表的后端（rear）進(jìn)行插入操作，和棧一樣虐骑，隊(duì)列是一種操作受限制的線性表准验。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭廷没。隊(duì)列中沒(méi)有元素時(shí)糊饱，稱為空隊(duì)列。
隊(duì)列的數(shù)據(jù)元素又稱為隊(duì)列元素颠黎。在隊(duì)列中插入一個(gè)隊(duì)列元素稱為入隊(duì)另锋，從隊(duì)列中刪除一個(gè)隊(duì)列元素稱為出隊(duì)。因?yàn)殛?duì)列只允許在一端插入狭归，在另一端刪除砰蠢，所以只有最早進(jìn)入隊(duì)列的元素才能最先從隊(duì)列中刪除，故隊(duì)列又稱為先進(jìn)先出（FIFO—first in first out）線性表唉铜。
比如我們?nèi)ル娪霸号抨?duì)買(mǎi)票，第一個(gè)進(jìn)入排隊(duì)序列的都是第一個(gè)買(mǎi)到票離開(kāi)隊(duì)列的人律杠，而最后進(jìn)入排隊(duì)序列排隊(duì)的都是最后買(mǎi)到票的潭流。
在比如在計(jì)算機(jī)操作系統(tǒng)中，有各種隊(duì)列在安靜的工作著柜去，比如打印機(jī)在打印列隊(duì)中等待打印灰嫉。
隊(duì)列分為：
①、單向隊(duì)列（Queue）：只能在一端插入數(shù)據(jù)嗓奢，另一端刪除數(shù)據(jù)讼撒。
②、雙向隊(duì)列（Deque）：每一端都可以進(jìn)行插入數(shù)據(jù)和刪除數(shù)據(jù)操作股耽。
這里我們還會(huì)介紹一種隊(duì)列——優(yōu)先級(jí)隊(duì)列根盒，優(yōu)先級(jí)隊(duì)列是比棧和隊(duì)列更專(zhuān)用的數(shù)據(jù)結(jié)構(gòu)，在優(yōu)先級(jí)隊(duì)列中物蝙，數(shù)據(jù)項(xiàng)按照關(guān)鍵字進(jìn)行排序炎滞，關(guān)鍵字最小（或者最大）的數(shù)據(jù)項(xiàng)往往在隊(duì)列的最前面诬乞，而數(shù)據(jù)項(xiàng)在插入的時(shí)候都會(huì)插入到合適的位置以確保隊(duì)列的有序册赛。
2钠导、Java模擬單向隊(duì)列實(shí)現(xiàn)
在實(shí)現(xiàn)之前，我們先看下面幾個(gè)問(wèn)題：
①森瘪、與棧不同的是牡属，隊(duì)列中的數(shù)據(jù)不總是從數(shù)組的0下標(biāo)開(kāi)始的，移除一些隊(duì)頭front的數(shù)據(jù)后扼睬，隊(duì)頭指針會(huì)指向一個(gè)較高的下標(biāo)位置逮栅，如下圖：
②、我們?cè)僭O(shè)計(jì)時(shí)痰驱，隊(duì)列中新增一個(gè)數(shù)據(jù)時(shí)证芭，隊(duì)尾的指針rear 會(huì)向上移動(dòng)，也就是向下標(biāo)大的方向担映。移除數(shù)據(jù)項(xiàng)時(shí)废士，隊(duì)頭指針 front 也會(huì)向下移動(dòng)。那么這樣設(shè)計(jì)好像和現(xiàn)實(shí)情況相反蝇完，比如排隊(duì)買(mǎi)電影票官硝，隊(duì)頭的買(mǎi)完票就離開(kāi)了，然后隊(duì)伍整體向前移動(dòng)短蜕。在計(jì)算機(jī)中也可以在隊(duì)列中刪除一個(gè)數(shù)之后氢架，隊(duì)列整體向前移動(dòng)，但是這樣做效率很差朋魔。我們選擇的做法是移動(dòng)隊(duì)頭和隊(duì)尾的指針岖研。
③、如果向第②步這樣移動(dòng)指針警检，相信隊(duì)尾指針很快就移動(dòng)到數(shù)據(jù)的最末端了孙援，這時(shí)候可能移除過(guò)數(shù)據(jù)，那么隊(duì)頭會(huì)有空著的位置扇雕，然后新來(lái)了一個(gè)數(shù)據(jù)項(xiàng)拓售，由于隊(duì)尾不能再向上移動(dòng)了，那該怎么辦呢镶奉？如下圖：
為了避免隊(duì)列不滿卻不能插入新的數(shù)據(jù)础淤，我們可以讓隊(duì)尾指針繞回到數(shù)組開(kāi)始的位置，這也稱為“循環(huán)隊(duì)列”哨苛。
弄懂原理之后鸽凶，Java實(shí)現(xiàn)代碼如下：
package com.ys.datastructure;
public class MyQueue {
private Object[] queArray;
//隊(duì)列總大小
private int maxSize;
//前端
private int front;
//后端
private int rear;
//隊(duì)列中元素的實(shí)際數(shù)目
private int nItems;
public MyQueue(int s){
maxSize = s;
queArray = new Object[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//隊(duì)列中新增數(shù)據(jù)
public void insert(int value){
if(isFull()){
System.out.println("隊(duì)列已滿！＝ㄇ汀吱瘩！");
}else{
//如果隊(duì)列尾部指向頂了，那么循環(huán)回來(lái)迹缀，執(zhí)行隊(duì)列的第一個(gè)元素
if(rear == maxSize -1){
rear = -1;
}
//隊(duì)尾指針加1使碾，然后在隊(duì)尾指針處插入新的數(shù)據(jù)
queArray[++rear] = value;
nItems++;
}
}
//移除數(shù)據(jù)
public Object remove(){
Object removeValue = null ;
if(!isEmpty()){
removeValue = queArray[front];
queArray[front] = null;
front++;
if(front == maxSize){
front = 0;
}
nItems--;
return removeValue;
}
return removeValue;
}
//查看對(duì)頭數(shù)據(jù)
public Object peekFront(){
return queArray[front];
}
//判斷隊(duì)列是否滿了
public boolean isFull(){
return (nItems == maxSize);
}
//判斷隊(duì)列是否為空
public boolean isEmpty(){
return (nItems ==0);
}
//返回隊(duì)列的大小
public int getSize(){
return nItems;
}
}
測(cè)試
package com.ys.test;
import com.ys.datastructure.MyQueue;
public class MyQueueTest {
public static void main(String[] args) {
MyQueue queue = new MyQueue(3);
queue.insert(1);
queue.insert(2);
queue.insert(3);//queArray數(shù)組數(shù)據(jù)為[1,2,3]
System.out.println(queue.peekFront()); //1
queue.remove();//queArray數(shù)組數(shù)據(jù)為[null,2,3]
System.out.println(queue.peekFront()); //2
queue.insert(4);//queArray數(shù)組數(shù)據(jù)為[4,2,3]
queue.insert(5);//隊(duì)列已滿,queArray數(shù)組數(shù)據(jù)為[4,2,3]
}
}
3蜜徽、雙端隊(duì)列
雙端隊(duì)列就是一個(gè)兩端都是結(jié)尾或者開(kāi)頭的隊(duì)列， 隊(duì)列的每一端都可以進(jìn)行插入數(shù)據(jù)項(xiàng)和移除數(shù)據(jù)項(xiàng)票摇，這些方法可以叫做：
insertRight()拘鞋、insertLeft()、removeLeft()矢门、removeRight()
如果嚴(yán)格禁止調(diào)用insertLeft()和removeLeft()（或禁用右端操作）盆色，那么雙端隊(duì)列的功能就和前面講的棧功能一樣。
如果嚴(yán)格禁止調(diào)用insertLeft()和removeRight(或相反的另一對(duì)方法)祟剔，那么雙端隊(duì)列的功能就和單向隊(duì)列一樣了隔躲。
4、優(yōu)先級(jí)隊(duì)列
優(yōu)先級(jí)隊(duì)列（priority queue）是比棧和隊(duì)列更專(zhuān)用的數(shù)據(jù)結(jié)構(gòu)物延，在優(yōu)先級(jí)隊(duì)列中宣旱，數(shù)據(jù)項(xiàng)按照關(guān)鍵字進(jìn)行排序，關(guān)鍵字最信咽怼（或者最大）的數(shù)據(jù)項(xiàng)往往在隊(duì)列的最前面浑吟，而數(shù)據(jù)項(xiàng)在插入的時(shí)候都會(huì)插入到合適的位置以確保隊(duì)列的有序。
優(yōu)先級(jí)隊(duì)列 是0個(gè)或多個(gè)元素的集合耗溜，每個(gè)元素都有一個(gè)優(yōu)先權(quán)组力，對(duì)優(yōu)先級(jí)隊(duì)列執(zhí)行的操作有：
（1）查找
（2）插入一個(gè)新元素
（3）刪除
一般情況下，查找操作用來(lái)搜索優(yōu)先權(quán)最大的元素抖拴，刪除操作用來(lái)刪除該元素 燎字。對(duì)于優(yōu)先權(quán)相同的元素，可按先進(jìn)先出次序處理或按任意優(yōu)先權(quán)進(jìn)行阿宅。
這里我們用數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列候衍，這種方法插入比較慢，但是它比較簡(jiǎn)單家夺，適用于數(shù)據(jù)量比較小并且不是特別注重插入速度的情況。
后面我們會(huì)講解堆伐弹，用堆的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列拉馋，可以相當(dāng)快的插入數(shù)據(jù)。
數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列惨好，聲明為int類(lèi)型的數(shù)組煌茴，關(guān)鍵字是數(shù)組里面的元素，在插入的時(shí)候按照從大到小的順序排列日川，也就是越小的元素優(yōu)先級(jí)越高蔓腐。
package com.ys.datastructure;
public class PriorityQue {
private int maxSize;
private int[] priQueArray;
private int nItems;
public PriorityQue(int s){
maxSize = s;
priQueArray = new int[maxSize];
nItems = 0;
}
//插入數(shù)據(jù)
public void insert(int value){
int j;
if(nItems == 0){
priQueArray[nItems++] = value;
}else{
j = nItems -1;
//選擇的排序方法是插入排序，按照從大到小的順序排列龄句，越小的越在隊(duì)列的頂端
while(j >=0 && value > priQueArray[j]){
priQueArray[j+1] = priQueArray[j];
j--;
}
priQueArray[j+1] = value;
nItems++;
}
}
//移除數(shù)據(jù),由于是按照大小排序的回论，所以移除數(shù)據(jù)我們指針向下移動(dòng)
//被移除的地方由于是int類(lèi)型的散罕，不能設(shè)置為null，這里的做法是設(shè)置為 -1
public int remove(){
int k = nItems -1;
int value = priQueArray[k];
priQueArray[k] = -1;//-1表示這個(gè)位置的數(shù)據(jù)被移除了
nItems--;
return value;
}
//查看優(yōu)先級(jí)最高的元素
public int peekMin(){
return priQueArray[nItems-1];
}
//判斷是否為空
public boolean isEmpty(){
return (nItems == 0);
}
//判斷是否滿了
public boolean isFull(){
return (nItems == maxSize);
}
}
insert() 方法傀蓉，先檢查隊(duì)列中是否有數(shù)據(jù)項(xiàng)欧漱，如果沒(méi)有，則直接插入到下標(biāo)為0的單元里葬燎，否則误甚，從數(shù)組頂部開(kāi)始比較，找到比插入值小的位置進(jìn)行插入谱净，并把 nItems 加1.
remove 方法直接獲取頂部元素窑邦。
優(yōu)先級(jí)隊(duì)列的插入操作需要 O(N)的時(shí)間，而刪除操作則需要O(1) 的時(shí)間壕探，后面會(huì)講解如何通過(guò) 堆 來(lái)改進(jìn)插入時(shí)間冈钦。
5、總結(jié)
本篇博客我們介紹了隊(duì)列的三種形式浩蓉，分別是單向隊(duì)列派继、雙向隊(duì)列以及優(yōu)先級(jí)隊(duì)列。其實(shí)大家聽(tīng)名字也可以聽(tīng)得出來(lái)他們之間的區(qū)別捻艳，單向隊(duì)列遵循先進(jìn)先出的原則驾窟，而且一端只能插入，另一端只能刪除认轨。雙向隊(duì)列則兩端都可插入和刪除绅络，如果限制雙向隊(duì)列的某一段的方法，則可以達(dá)到和單向隊(duì)列同樣的功能嘁字。最后優(yōu)先級(jí)隊(duì)列恩急，則是在插入元素的時(shí)候進(jìn)行了優(yōu)先級(jí)別排序，在實(shí)際應(yīng)用中單項(xiàng)隊(duì)列和優(yōu)先級(jí)隊(duì)列使用的比較多纪蜒。后面講解了堆這種數(shù)據(jù)結(jié)構(gòu)衷恭，我們會(huì)用堆來(lái)實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，改善優(yōu)先級(jí)隊(duì)列插入元素的時(shí)間纯续。
通過(guò)前面講的棧以及本篇講的隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)随珠，我們稍微總結(jié)一下：
①、棧猬错、隊(duì)列（單向隊(duì)列）窗看、優(yōu)先級(jí)隊(duì)列通常是用來(lái)簡(jiǎn)化某些程序操作的數(shù)據(jù)結(jié)構(gòu)，而不是主要作為存儲(chǔ)數(shù)據(jù)的倦炒。
②显沈、在這些數(shù)據(jù)結(jié)構(gòu)中，只有一個(gè)數(shù)據(jù)項(xiàng)可以被訪問(wèn)逢唤。
③拉讯、棧允許在棧頂壓入（插入）數(shù)據(jù)涤浇，在棧頂彈出（移除）數(shù)據(jù)，但是只能訪問(wèn)最后一個(gè)插入的數(shù)據(jù)項(xiàng)遂唧，也就是棧頂元素芙代。
④、隊(duì)列（單向隊(duì)列）只能在隊(duì)尾插入數(shù)據(jù)盖彭，對(duì)頭刪除數(shù)據(jù)纹烹，并且只能訪問(wèn)對(duì)頭的數(shù)據(jù)。而且隊(duì)列還可以實(shí)現(xiàn)循環(huán)隊(duì)列召边，它基于數(shù)組铺呵，數(shù)組下標(biāo)可以從數(shù)組末端繞回到數(shù)組的開(kāi)始位置。
⑤隧熙、優(yōu)先級(jí)隊(duì)列是有序的插入數(shù)據(jù)片挂，并且只能訪問(wèn)當(dāng)前元素中優(yōu)先級(jí)別最大（或最小）的元素贞盯。
⑥音念、這些數(shù)據(jù)結(jié)構(gòu)都能由數(shù)組實(shí)現(xiàn)，但是可以用別的機(jī)制（后面講的鏈表躏敢、堆等數(shù)據(jù)結(jié)構(gòu)）實(shí)現(xiàn)闷愤。
