文章轉(zhuǎn)自：https://www.cnblogs.com/ysocean/p/7921930.html#_label0
1、隊(duì)列的基本概念
隊(duì)列（queue）是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時(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ì)買票，第一個(gè)進(jìn)入排隊(duì)序列的都是第一個(gè)買到票離開隊(duì)列的人，而最后進(jìn)入排隊(duì)序列排隊(duì)的都是最后買到票的。
在比如在計(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ì)列更專用的數(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è)問題：
①、與棧不同的是，隊(duì)列中的數(shù)據(jù)不總是從數(shù)組的0下標(biāo)開始的，移除一些隊(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ì)買電影票，隊(duì)頭的買完票就離開了，然后隊(duì)伍整體向前移動(dòng)。在計(jì)算機(jī)中也可以在隊(duì)列中刪除一個(gè)數(shù)之后，隊(duì)列整體向前移動(dòng)，但是這樣做效率很差。我們選擇的做法是移動(dòng)隊(duì)頭和隊(duì)尾的指針。
③、如果向第②步這樣移動(dòng)指針，相信隊(duì)尾指針很快就移動(dòng)到數(shù)據(jù)的最末端了，這時(shí)候可能移除過數(shù)據(jù)，那么隊(duì)頭會(huì)有空著的位置，然后新來了一個(gè)數(shù)據(jù)項(xiàng)，由于隊(duì)尾不能再向上移動(dòng)了，那該怎么辦呢？如下圖：
為了避免隊(duì)列不滿卻不能插入新的數(shù)據(jù)，我們可以讓隊(duì)尾指針繞回到數(shù)組開始的位置，這也稱為“循環(huán)隊(duì)列”。
弄懂原理之后，Java實(shí)現(xiàn)代碼如下：
public class MyQueue {
private Object[] queArray;
//隊(duì)列總大小
private int maxSize;
//前端指針
private int front;
//后端指針
private int rear;
//對(duì)列中的元素的實(shí)際數(shù)目
private int nItems;
/**
* 初始化隊(duì)列
* @param s
*/
public MyQueue(int s) {
maxSize=s;
queArray=new Object[maxSize];
front=0;
rear=-1;
nItems=0;
}
//隊(duì)列中新增元素
public void insert(int value) {
if(isFull()) {
System.err.println("隊(duì)列已滿");
}else {
//如果對(duì)尾指針等于數(shù)組最后一個(gè)，放在數(shù)組第一個(gè)位置
if(rear==maxSize-1)
rear=-1;
//對(duì)尾指針+1，然后在對(duì)尾指針處插入新的數(shù)據(jù)
queArray[++rear]=value;
//隊(duì)列個(gè)數(shù)+1
nItems++;
}
}
//移除數(shù)據(jù),只能移除對(duì)頭的數(shù)據(jù)
public Object remove() {
Object removeValue = null ;
if(!isEmpty()) {
removeValue=queArray[front];
queArray[front]=null;
front++;
//如果對(duì)頭指針等于數(shù)組大小隊(duì)列已經(jīng)為空，將指針初始化
if(front==maxSize) {
front=0;
rear=-1;
}
nItems--;
return removeValue;
}
return removeValue;
}
//查看對(duì)頭數(shù)據(jù)
public Object peekFront() {
return queArray[front];
}
//判斷隊(duì)列是否滿了
public boolean isFull() {
//隊(duì)列中的實(shí)際個(gè)數(shù)等于隊(duì)列大小時(shí)判斷隊(duì)列已滿
return (nItems==maxSize);
}
//判斷隊(duì)列是否為空
public boolean isEmpty() {
return (nItems==0);
}
//返回隊(duì)列的大小
public int getSize() {
return nItems;
}
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é)尾或者開頭的隊(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ì)列更專用的數(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）刪除
一般情況下，查找操作用來搜索優(yōu)先權(quán)最大的元素，刪除操作用來刪除該元素 。對(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)來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，可以相當(dāng)快的插入數(shù)據(jù)。
數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，聲明為int類型的數(shù)組，關(guān)鍵字是數(shù)組里面的元素，在插入的時(shí)候按照從大到小的順序排列，也就是越小的元素優(yōu)先級(jí)越高。
public class PriorityQue {
//數(shù)組實(shí)際大小
private int maxSize;
private int[] priQueArray;
//隊(duì)列中的數(shù)據(jù)個(gè)數(shù)
private int nItems;
public PriorityQue(int s){
maxSize = s;
priQueArray = new int[maxSize];
nItems = 0;
}
//插入數(shù)據(jù)
public void insert(int value) {
int j;
//如果隊(duì)列中的個(gè)數(shù)為是0
if(nItems==0) {
priQueArray[nItems++] = value;
}else {
j=nItems-1;
//如果插入的值大于隊(duì)列中最后一個(gè)
while(j>=0 && value>priQueArray[j]) {
priQueArray[j+1] = priQueArray[j];
j--;
}
priQueArray[j+1] = value;
nItems++;
}
}
//移除數(shù)據(jù),由于是按照大小排序的，所以移除數(shù)據(jù)我們指針向下移動(dòng)
//被移除的地方由于是int類型的，不能設(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)，如果沒有，則直接插入到下標(biāo)為0的單元里，否則，從數(shù)組頂部開始比較，找到比插入值小的位置進(jìn)行插入，并把 nItems 加1.
remove 方法直接獲取頂部元素。
優(yōu)先級(jí)隊(duì)列的插入操作需要 O(N)的時(shí)間，而刪除操作則需要O(1) 的時(shí)間，后面會(huì)講解如何通過 堆 來改進(jìn)插入時(shí)間。
5、總結(jié)
本篇博客我們介紹了隊(duì)列的三種形式，分別是單向隊(duì)列、雙向隊(duì)列以及優(yōu)先級(jí)隊(duì)列。其實(shí)大家聽名字也可以聽得出來他們之間的區(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ì)用堆來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，改善優(yōu)先級(jí)隊(duì)列插入元素的時(shí)間。
通過前面講的棧以及本篇講的隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)，我們稍微總結(jié)一下：
①、棧、隊(duì)列（單向隊(duì)列）、優(yōu)先級(jí)隊(duì)列通常是用來簡(jiǎn)化某些程序操作的數(shù)據(jù)結(jié)構(gòu)，而不是主要作為存儲(chǔ)數(shù)據(jù)的。
②、在這些數(shù)據(jù)結(jié)構(gòu)中，只有一個(gè)數(shù)據(jù)項(xiàng)可以被訪問。
③、棧允許在棧頂壓入（插入）數(shù)據(jù)，在棧頂彈出（移除）數(shù)據(jù)，但是只能訪問最后一個(gè)插入的數(shù)據(jù)項(xiàng)，也就是棧頂元素。
④、隊(duì)列（單向隊(duì)列）只能在隊(duì)尾插入數(shù)據(jù)，對(duì)頭刪除數(shù)據(jù)，并且只能訪問對(duì)頭的數(shù)據(jù)。而且隊(duì)列還可以實(shí)現(xiàn)循環(huán)隊(duì)列，它基于數(shù)組，數(shù)組下標(biāo)可以從數(shù)組末端繞回到數(shù)組的開始位置。
⑤、優(yōu)先級(jí)隊(duì)列是有序的插入數(shù)據(jù)，并且只能訪問當(dāng)前元素中優(yōu)先級(jí)別最大（或最?。┑脑?。
⑥、這些數(shù)據(jù)結(jié)構(gòu)都能由數(shù)組實(shí)現(xiàn)，但是可以用別的機(jī)制（后面講的鏈表、堆等數(shù)據(jù)結(jié)構(gòu)）實(shí)現(xiàn)。
