數據結構之隊列_數據分析師

棧是“后進先出”（LIFO，Last InFirst Out）的數據結構，與之相反，隊列是“先進先出”（FIFO，First InFirst Out）的數據結構。

隊列的作用就像售票口前的人們站成的一排一樣：第一個進入隊列的人將最先買到票，最后排隊的人最后才能買到票。

在計算機操作系統或網路中，有各種隊列在安靜地工作著。打印作業在打印隊列中等待打印。當敲擊鍵盤時，也有一個存儲鍵盤鍵入內容的隊列，如果我們敲 擊了一個鍵，而計算機又暫時在做其他事情，敲擊的內容不會丟失，它會排在隊列中等待，直到計算機有時間來讀取它，利用隊列保證了鍵入內容在處理時其順序不 會改變。

棧的插入和刪除數據項的命名方法很標準，成為push和pop，隊列的方法至今也沒有一個標準化的方法，插入可以稱作put、add或enque等，刪除可以叫作delete、get、remove或deque等。

隊列

下面我們依然使用數組作為底層容器來實現一個隊列的操作封裝，與棧不同的是，隊列的數據項并不都是從數組的第一個下標開始，因為數據項在數組的下標越小代表其在隊列中的排列越靠前，移除數據項只能從隊頭移除，然后隊頭指針后移，這樣數組的前幾個位置就會空出來如下圖所示：

這與我們的直觀感覺相反，因為我們排隊買票時，隊列總是向前移動，當前面的人買完票離開后，其他人都向前移動，而在我們的設計中，隊列并沒有向前移動，因為那樣做會使效率大打折扣，我們只需要使用指針來標記隊頭和隊尾，隊列發生變化時，移動指針就可以，而數據項的位置不變。

但是，這樣的設計還存在著一個問題，隨著隊頭元素不斷地移除，數組前面空出的位置會越來越多，當隊尾指針移到最后的位置時，即使隊列沒有滿，我們也不能再插入新的數據項了。

解決這種缺點的方法是環繞式處理，即讓隊尾指針回到數組的第一個位置：

這就是循環隊列（也成為緩沖環）。雖然在存儲上是線形的，但是在邏輯上它是一個首尾銜接的環形。

[java] view plaincopyprint?

1. public class Queue { 
2.        
3.       private int [] queArray; 
4.       private int maxSize; 
5.       public int front;   //存儲隊頭元素的下標 
6.       public int rear;    //存儲隊尾元素的下標 
7.       private int length; //隊列長度 
8.        
9.       //構造方法，初始化隊列 
10.       public Queue(int maxSize){ 
11.              this.maxSize = maxSize; 
12.              queArray = new int [maxSize]; 
13.              front = 0; 
14.              rear = -1; 
15.              length = 0; 
16.       } 
17.        
18.       //插入 
19.       public void insert(int elem) throwsException{ 
20.              if(isFull()){ 
21.                     throw new Exception("隊列已滿，不能進行插入操作！"); 
22.              } 
23.              //如果隊尾指針已到達數組的末端，插入到數組的第一個位置 
24.              if(rear == maxSize-1){ 
25.                     rear = -1; 
26.              } 
27.              queArray[++rear] = elem; 
28.              length++; 
29.       } 
30.        
31.       //移除 
32.       public int remove() throws Exception{ 
33.              if(isEmpty()){ 
34.                     throw new Exception("隊列為空，不能進行移除操作！"); 
35.              } 
36.              int elem = queArray[front++]; 
37.              //如果隊頭指針已到達數組末端，則移到數組第一個位置 
38.              if(front == maxSize){ 
39.                     front = 0; 
40.              } 
41.              length--; 
42.              returnelem; 
43.       } 
44.        
45.       //查看隊頭元素 
46.       public int peek() throws Exception{ 
47.              if(isEmpty()){ 
48.                     throw new Exception("隊列內沒有元素！"); 
49.              } 
50.              return queArray[front]; 
51.       } 
52.        
53.       //獲取隊列長度 
54.       public int size(){ 
55.              return length; 
56.       } 
57.        
58.       //判空 
59.       public boolean isEmpty(){ 
60.              return (length == 0); 
61.       } 
62.        
63.       //判滿 
64.       public boolean isFull(){ 
65.              return (length == maxSize); 
66.       } 
67.        
68. } 

還有一種稱為雙端隊列的數據結構，隊列的每一端都可以進行插入和移除操作。

其實雙端隊列是隊列和棧的綜合體。如果限制雙端隊列的一段只能插入，而另一端只能移除，就變成了平常意義上的隊列；如果限制雙端隊列只能在一端進行插入和移除，就變成了棧。

優先級隊列

像普通隊列一樣，優先級隊列有一個隊頭和一個隊尾，并且也是從隊頭移除數據，從隊尾插入數據，不同的是，在優先級隊列中，數據項按關鍵字的值排序，數據項插入的時候會按照順序插入到合適的位置。

除了可以快速訪問優先級最高的數據項，優先級隊列還應該可以實現相當快的插入，因此，優先級隊列通常使用一種稱為堆的數據結構來實現。在下例中，簡便起見，我們仍然使用數組來實現

在數據項個數比較少，或不太關心速度的情況下，用數組實現優先級隊列還可以滿足要求，如果數據項很多，或對速度要求很高，采用堆是更好的選擇

優先級隊列的實現跟上面普通隊列的實現有很大的區別。

優先級隊列的插入本來就需要移動元素來找到應該插入的位置，所以循環隊列那種不需要移動元素的優勢就不太明顯了。在下例中，沒有設置隊頭和隊尾指 針，而是使數組的第一個元素永遠是隊尾，數組的最后一個元素永遠是隊頭，為什么不是相反的呢？因為隊頭有移除操作，所以將隊頭放在數組的末端，便于移除， 如果放在首段，每次移除隊頭都需要將隊列向前移動。

                                                                                  插入元素示意圖

                                                                                                移除元素示意圖

在下例中，我們設置了一個基準點，認為元素到里基準點的距離越近則優先級越高，如設置的基準點為2，3到2的距離就是|3-2|=1，而-1到2的距離是|-1-2|=3，所以2的優先級就比-1要高。

[java] view plaincopyprint?

1. public class PriorityQueue { 
2.        
3.       private int [] queArray; 
4.       private int maxSize; 
5.       private int length; //隊列長度 
6.       private int referencePoint;  //基準點 
7.        
8.       //構造方法，初始化隊列 
9.       public PriorityQueue(int maxSize,intreferencePoint){ 
10.              this.maxSize= maxSize; 
11.              this.referencePoint =referencePoint; 
12.              queArray = new int [maxSize]; 
13.              length = 0; 
14.       } 
15.        
16.       //插入 
17.       public void insert(int elem) throwsException{ 
18.              if(isFull()){ 
19.                     throw new Exception("隊列已滿，不能進行插入操作！"); 
20.              } 
21.              
22.              //如果隊列為空，插入到數組的第一個位置 
23.              if(length == 0){ 
24.                     queArray[length++] = elem; 
25.              }else{ 
26.                     int i; 
27.                     for(i=length;i>0;i--){ 
28.                            
29.                            int dis =Math.abs(elem-referencePoint);  //待插入元素的距離 
30.                            int curDis =Math.abs(queArray[i-1]-referencePoint); //當前元素的距離 
31.                            
32.                            //將比插入元素優先級高的元素后移一位 
33.                            if(dis>= curDis){ 
34.                                   queArray[i] =queArray[i-1]; 
35.                            }else{ 
36.                                   break; 
37.                            } 
38.                     } 
39.                     queArray[i] = elem; 
40.                     length++; 
41.              } 
42.       } 
43.        
44.       //移除 
45.       public int remove() throws Exception{ 
46.              if(isEmpty()){ 
47.                     throw new Exception("隊列為空，不能進行移除操作！"); 
48.              } 
49.              int elem = queArray[--length]; 
50.              return elem; 
51.       } 
52.        
53.       //查看隊頭元素 
54.       public int peek() throws Exception{ 
55.              if(isEmpty()){ 
56.                     throw new Exception("隊列內沒有元素！"); 
57.              } 
58.              return queArray[length-1]; 
59.       } 
60.        
61.       //返回隊列長度 
62.       public int size(){ 
63.              return length; 
64.       } 
65.        
66.       //判空 
67.       public boolean isEmpty(){ 
68.              return (length == 0); 
69.       } 
70.        
71.       //判滿 
72.       public boolean isFull(){ 
73.              return (length == maxSize); 
74.       } 
75.        
76. }