經典演演算法題每日演練——第十九題雙端佇列

話說大學的時候老師說妹子比工作重要~，工作可以再換，妹子這個。。。所以。。。這兩個月也就一直忙著 Fall in love，嗨，慢慢調整心態吧，
這篇就選一個簡單的資料結構聊一聊，話說有很多資料結構都在玩組合拳，比如說：塊狀連結串列，塊狀陣列，當然還有本篇的雙端佇列，是的，它就是
棧和佇列的組合體。
一：概念
我們知道普通佇列是限制級的一端進，另一端出的 FIFO 形式，棧是一端進出的 LIFO 形式，而雙端佇列就沒有這樣的限制級，也就是我們可以在
佇列兩端進行插入或者刪除操作。
二：編碼
1：定義結構體
通常情況下，佇列的內部都是採用陣列來實現，而且帶有兩個指標 head 和 tail 來指向陣列的區間段，為了充分利用陣列空間，我們也會用% 來實
現邏輯上的迴圈陣列，如下圖。

1 public class MyQueue
2 {
3 public int head;
4
5 public int tail;
6
7 public int maxSize;
8
9 public int size;
10
11 public T[] list;
12
13 public MyQueue()
14 {
15 head = tail = size = 0;
16 maxSize = 3;
17 list = new T[maxSize];
18 }
19 }

這裡有一個注意的細節就是 “size 欄位 “，它是為了方便統計佇列是否為滿或者佇列是否為空。
2：隊尾入隊
剛才也說了，雙端佇列是可以在佇列的兩端進行插入和刪除的，要注意的是我們用 head 和 tail 指標的時候，tail 指標是指向元素的下一個位置，
而 head 指標是指向當前元素，所以我們可以從 tail 端 push 資料的時候只要” 順時針 “下移一個位置即可。

1 ///

2 /// 隊尾入隊
3 ///

4 /// 5 ///
6 public bool Push_Tail(T t)
7 {
8 //判斷佇列是否已滿
9 if (myQueue.size == myQueue.list.Length)
10 return false;
11
12 myQueue.list[myQueue.tail] = t;
13
14 //順時針旋轉
15 myQueue.tail = (myQueue.tail + 1) % myQueue.maxSize;
16
17 myQueue.size++;
18
19 return true;
20 }

3：隊尾出隊
和隊尾入隊一樣，我們只要將 tail 指標” 逆時針 “下移一個位置，當然有一個細節需要注意，就是 tail 指標有存在負值的情況，畢竟我們是做”–操作 “的，
所以需要 tail+maxSize，即：myQueue.tail = (–myQueue.tail + myQueue.maxSize) % myQueue.maxSize;

1 ///

2 /// 隊尾出隊
3 ///

4 /// 5 /// 6 public T Pop_Tail()
7 {
8 //判斷佇列是否已空
9 if (myQueue.size == 0)
10 return default(T);
11
12 //逆時針旋轉 (防止負數)
13 myQueue.tail = (–myQueue.tail + myQueue.maxSize) % myQueue.maxSize;
14
15 var temp = myQueue.list[myQueue.tail];
16
17 //賦予空值
18 myQueue.list[myQueue.tail] = default(T);
19
20 myQueue.size–;
21
22 return temp;
23 }

4：隊首入隊
從 head 端來說，我們 push 資料的時候是 head 指標 “逆時針” 旋轉，要注意的是同樣要防止負數的產生，並且 head 指標是指向當前元素。

1 ///

2 /// 隊首入隊
3 ///

4 /// 5 ///
6 public bool Push_Head(T t)
7 {
8 //判斷佇列是否已滿
9 if (myQueue.size == myQueue.list.Length)
10 return false;
11
12 //逆時針旋轉 (防止負數產生)
13 myQueue.head = (–myQueue.head + myQueue.maxSize) % myQueue.maxSize;
14
15 //賦予元素
16 myQueue.list[myQueue.head] = t;
17
18 myQueue.size++;
19
20 return true;
21 }

5：隊首出隊
說到這個方法，我想大家應該都懂了雙端佇列的大概流程了，這個方法我也不用贅敘了。

1 ///

2 /// 隊首出隊
3 ///

4 /// 5 /// 6 public T Pop_Head()
7 {
8 //判斷佇列是否已空
9 if (myQueue.size == 0)
10 return default(T);
11
12 //獲取隊首元素
13 var temp = myQueue.list[myQueue.head];
14
15 //原來單位的值賦預設值
16 myQueue.list[myQueue.head] = default(T);
17
18 //順時針旋轉
19 myQueue.head = (myQueue.head + 1) % myQueue.maxSize;
20
21 myQueue.size–;
22
23 return temp;
24 }

從上面的四個方法可以看出：
當我們只使用 Push_Tail 和 Pop_Tail 的話，那它就是棧。
當我們只使用 Push_Tail 和 Pop_Head 的話，那它就是佇列。
最後是全部程式碼：

1 using System.Net;
2 using System;
3 using System.IO;
4 using System.Collections.Generic;
5 using System.Text;
6 using System.Drawing;
7 using System.Drawing.Imaging;
8
9 class Program
10 {
11 static void Main(string[] args)
12 {
13 DoubleQueue queue = new DoubleQueue();
14
15 queue.Push_Tail(10);
16 queue.Push_Tail(20);
17 queue.Push_Tail(30);
18
19 queue.Pop_Tail();
20 queue.Pop_Tail();
21 queue.Pop_Tail();
22
23 queue.Push_Tail(10);
24 queue.Push_Head(20);
25 queue.Push_Head(30);
26 queue.Push_Head(30);
27
28 queue.Pop_Tail();
29 queue.Pop_Tail();
30 queue.Pop_Head();
31
32 queue.Push_Head(40);
33 queue.Push_Tail(50);
34 queue.Push_Tail(60);
35 }
36 }
37
38 ///

39 /// 雙端佇列
40 ///

41 public class DoubleQueue
42 {
43 public class MyQueue
44 {
45 public int head;
46
47 public int tail;
48
49 public int maxSize;
50
51 public int size;
52
53 public T[] list;
54
55 public MyQueue()
56 {
57 head = tail = size = 0;
58 maxSize = 3;
59 list = new T[maxSize];
60 }
61 }
62
63 MyQueue myQueue = new MyQueue();
64
65 ///

66 /// 隊尾入隊
67 ///

68 /// 69 ///
70 public bool Push_Tail(T t)
71 {
72 //判斷佇列是否已滿
73 if (myQueue.size == myQueue.list.Length)
74 return false;
75
76 myQueue.list[myQueue.tail] = t;
77
78 //順時針旋轉
79 myQueue.tail = (myQueue.tail + 1) % myQueue.maxSize;
80
81 myQueue.size++;
82
83 return true;
84 }
85
86 ///

87 /// 隊尾出隊
88 ///

89 /// 90 /// 91 public T Pop_Tail()
92 {
93 //判斷佇列是否已空
94 if (myQueue.size == 0)
95 return default(T);
96
97 //逆時針旋轉 (防止負數)
98 myQueue.tail = (–myQueue.tail + myQueue.maxSize) % myQueue.maxSize;
99
100 var temp = myQueue.list[myQueue.tail];
101
102 //賦予空值
103 myQueue.list[myQueue.tail] = default(T);
104
105 myQueue.size–;
106
107 return temp;
108 }
109
110 ///

111 /// 隊首入隊
112 ///

113 /// 114 ///
115 public bool Push_Head(T t)
116 {
117 //判斷佇列是否已滿
118 if (myQueue.size == myQueue.list.Length)
119 return false;
120
121 //逆時針旋轉 (防止負數產生)
122 myQueue.head = (–myQueue.head + myQueue.maxSize) % myQueue.maxSize;
123
124 //賦予元素
125 myQueue.list[myQueue.head] = t;
126
127 myQueue.size++;
128
129 return true;
130 }
131
132 ///

133 /// 隊首出隊
134 ///

135 /// 136 /// 137 public T Pop_Head()
138 {
139 //判斷佇列是否已空
140 if (myQueue.size == 0)
141 return default(T);
142
143 //獲取隊首元素
144 var temp = myQueue.list[myQueue.head];
145
146 //原來單位的值賦預設值
147 myQueue.list[myQueue.head] = default(T);
148
149 //順時針旋轉
150 myQueue.head = (myQueue.head + 1) % myQueue.maxSize;
151
152 myQueue.size–;
153
154 return temp;
155 }
156 }