大話資料結構八：隊列的順序存儲結構（循環隊列）

1. 什麼是隊列？

隊列(queue)是隻允許在一端進行插入操作，而在另一端進行删除操作的線性表。

2. 隊列的特點:

隊列是一種先進先出(First In First out)的線性表，允許插入的一端稱為隊尾，允許删除的一端稱為隊頭。

3. 隊列順序存儲有什麼不足？

使用數組實作的順序存儲，當做出隊列操作時，所有的元素都需要向前移動一位，性能很低。

4. 什麼是循環隊列？

隊列頭尾相接的順序存儲結構稱為循環隊列。

如圖所示：front記住隊頭元素下标，rear記住隊尾元素的下一個元素。

注意：

1. 隻憑等式front=rear是無法判斷隊空還是隊滿，是以我們約定當隊列頭指針front在隊尾指針rear的下一個位置上時,作為隊列"已滿"的标志，當隊列滿時,數組中還會有一個空閑位置。

2. 我們也可以設定一個标志變量flag，當（front == rear && flag == 0） 隊列為空， 當（front == rear && flag == 1）隊列為滿。

5. Java使用數組實作循環隊列:

[java]  view plain  copy  

1. //循環隊列的順序存儲結構（數組實作）  
2. public class LoopQueue<T> {  
3.     private Object[] arr; // 對象數組，隊列最多存儲  
4.     private int front; // 記住隊首下标位置  
5.     private int rear; // 記住隊尾下标的下一個位置  
6.     private static final int DEFAULT_SIZE = 3; // 定義數組預設長度  
7.     public LoopQueue() {  
8.         this(DEFAULT_SIZE);  
9.     }  
10.     public LoopQueue(int size) {  
11.         arr = new Object[size];  
12.         front = 0;  
13.         rear = 0;  
14.     }  
15.     // 将元素追加到隊列尾部  
16.     public boolean enqueue(T data) {  
17.         if ((rear + 1) % arr.length == front) { // 判斷隊列是否已滿  
18.             System.out.println("隊列已滿,無法入隊..");  
19.             return false;  
20.         }  
21.         arr[rear] = data; // 将元素data指派到隊尾  
22.         System.out.println(data + "入隊..");  
23.         rear = (rear + 1) % arr.length; // real下标向後移一位,若到最後則轉到數組頭部  
24.         return true;  
25.     }  
26.     // 隊列頭部的第一個元素出隊  
27.     @SuppressWarnings("unchecked")  
28.     public T dequeue() {  
29.         if (rear == front) { // 判斷隊列是否為空  
30.             System.out.println("隊列已空,無法出隊..");  
31.             return null;  
32.         }  
33.         Object data = arr[front];  
34.         System.out.println(data + "出隊..");  
35.         front = (front + 1) % arr.length; // front下标向後移一位,若到最後則轉到數組頭部  
36.         return (T) data;  
37.     }  
38.     // 擷取隊列中元素個數  
39.     public int size() {  
40.         return (rear - front + arr.length) % arr.length;  
41.     }  
42.     public static void main(String[] args) {  
43.         LoopQueue<String> queue = new LoopQueue<String>();  
44.         queue.enqueue("張三");  
45.         queue.dequeue();  
46.         queue.enqueue("李四");  
47.         queue.enqueue("王五");  
48.         queue.enqueue("趙六");  
49.         queue.dequeue();  
50.         queue.enqueue("田七");  
51.         queue.dequeue();  
52.         queue.enqueue("周八");  
53.         System.out.println("隊列中元素個數為: " + queue.size());  
54.     }  
55. }  

6. 循環隊列的不足:

如果隻是順序存儲，算法的性能不咋的，但是循環隊列卻不得不面臨數組可能溢出的問題，有什麼好的解決辦法嗎？

請見下節 -- 鍊隊列，未完待續 . . .