隊(duì)列簡(jiǎn)介：
隊(duì)列（Queue）是一種數(shù)據(jù)結(jié)構(gòu)，可以在隊(duì)列的一端插入元素而在隊(duì)列的另一端刪除元素。
?。?1 ）允許刪除的一端稱為 隊(duì)頭（ Front ） 。
?。?2 ）允許插入的一端稱為 隊(duì)尾（ Rear ） 。
?。?3 ）當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為 空隊(duì)列 。
?。?4 ）隊(duì)列亦稱作先進(jìn)先出（ First In First Out ）的線性表，簡(jiǎn)稱為 FIFO 表 。
隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。新來(lái)的成員總是加入隊(duì)尾（即不允許 " 加塞 " ），每次離開(kāi)的成員總是隊(duì)列頭上的（不允許中途離隊(duì)），即當(dāng)前 " 最老的 " 成員離隊(duì)。
多任務(wù)系統(tǒng)是一個(gè)典型的隊(duì)列示例，在其中完成作業(yè)的調(diào)度。假設(shè)有五個(gè)程序等待執(zhí)行， 它們將被放入一個(gè)隊(duì)列，如果有第六個(gè)程序要執(zhí)行，它將被放在隊(duì)列的末尾。隊(duì)列中首位的程序首先執(zhí)行。
隊(duì)列實(shí)現(xiàn)：
1 /*
2
3 （1）initQueue（Q）
4 置空隊(duì)。構(gòu)造一個(gè)空隊(duì)列Q。
5
6 （2）isEmpty（Q）
7 判斷隊(duì)列是否空。若隊(duì)列Q為空，則返回真值，否則返回假值。
8
9 （3）isFull(Q)
10 判斷隊(duì)列是否以滿, 以滿返回true, 沒(méi)滿則返回flase
11
12 （4） addQueue（Q，x）
13 若隊(duì)列Q非滿，則將元素x插入Q的隊(duì)尾。此操作簡(jiǎn)稱 入隊(duì) 。
14
15 （5） DelQueue（Q）
16 若隊(duì)列Q非空，則刪去Q的隊(duì)頭元素，并返回該元素。此操作簡(jiǎn)稱 出隊(duì) 。
17
18 （6） queueFront（Q）
19 若隊(duì)列Q非空，則返回隊(duì)頭元素，但不改變隊(duì)列Q的狀態(tài)。
20
21 （7） queueDisplay（Q）
22 顯示隊(duì)列中的元素。
23 */
24
25 #include "iostream.h"
26
27 #define maxSize 10 // 存儲(chǔ)數(shù)據(jù)大小, 可以隨便設(shè)定值
28
29 struct Queue
30 {
31 int data[maxSize];
32 int front; // 隊(duì)首
33 int rear; // 隊(duì)尾
34 };
35
36 void initQueue( Queue &Q );
37 bool isEmpty( Queue &Q );
38 bool isFull( Queue &Q );
39 bool addQueue( Queue &Q, int x );
40 bool delQueue( Queue &Q );
41 int queueFront( Queue &Q );
42 bool queueDisplay( Queue &Q );
43
44 int main( void )
45 {
46 int i;
47 int num;
48 Queue Q;
49
50 initQueue( Q ); // 初始化隊(duì)列
51
52 cout << "輸入入隊(duì)10個(gè)數(shù)" << endl;
53 /* 入隊(duì) */
54 for ( i = 0; i < 10; i++ )
55 {
56 cin >> num;
57 if ( addQueue( Q, num ) == false )
58 {
59 cout << "隊(duì)列以滿!" << endl;
60 }
61 }
62
63 cout << "隊(duì)頭: " << queueFront( Q ) << endl; // 顯示隊(duì)頭
64 cout << "隊(duì)列所有元素:" << endl;
65 if ( queueDisplay( Q ) == false ) // 顯示隊(duì)列所有元素
66 {
67 cout << "隊(duì)列為空!" << endl;
68 }
69
70 /* 出隊(duì) */
71 for ( i = 0; i < 5; i++ )
72 {
73 if ( delQueue( Q ) == false )
74 {
75 cout << "隊(duì)列以空" << endl;
76 }
77 }
78
79 cout << endl;
80 cout << endl;
81 cout << "================== 出隊(duì)以后 ===========================" << endl;
82 cout << "出隊(duì)后隊(duì)頭: " << queueFront( Q ) << endl; // 顯示隊(duì)頭
83 cout << "出隊(duì)后隊(duì)列所有元素:" << endl;
84 if ( queueDisplay( Q ) == false ) // 顯示隊(duì)列所有元素
85 {
86 cout << "隊(duì)列為空!" << endl;
87 }
88
89 cout << endl;
90 cout << "輸入入隊(duì)5個(gè)數(shù)" << endl;
91 /* 再入隊(duì) */
92 for ( i = 0; i < 5; i++ )
93 {
94 cin >> num;
95 if ( addQueue( Q, num ) == false )
96 {
97 cout << "隊(duì)列以滿!" << endl;
98 }
99 }
100
101 cout << endl;
102 cout << endl;
103 cout << "================== 入隊(duì)以后 ===========================" << endl;
104 cout << "入隊(duì)后隊(duì)頭: " << queueFront( Q ) << endl; // 顯示隊(duì)頭
105 cout << "入隊(duì)后隊(duì)列所有元素:" << endl;
106 if ( queueDisplay( Q ) == false ) // 顯示隊(duì)列所有元素
107 {
108 cout << "隊(duì)列為空!" << endl;
109 }
110 return 0;
111 }
112
113 /* 初始化隊(duì)列 */
114 void initQueue( Queue &Q )
115 {
116 int i;
117
118 for ( i = 0; i < maxSize; i++ )
119 {
120 Q.data[i] = 0; // 初始值都為0
121 Q.front = 0;
122 Q.rear = 0;
123 }
124 }
125
126 /* 判斷隊(duì)列是否為空, 為空返回true, 不為空則返回flase */
127 bool isEmpty( Queue &Q )
128 {
129 if ( Q.front != 0 ) // 如果隊(duì)頭不等于0,則表示不為空
130 {
131 return false;
132 }
133
134 return true;
135 }
136
137 /* 判斷隊(duì)列是否以滿, 以滿返回true, 沒(méi)滿則返回flase */
138 bool isFull( Queue &Q )
139 {
140 if ( Q.data[maxSize - 1] == 0 ) // 如果隊(duì)尾等于0,則表示隊(duì)列沒(méi)滿
141 {
142 return false;
143 }
144
145 return true;
146 }
147
148 /* 若隊(duì)列Q非滿,則將元素x插入Q的隊(duì)尾.此操作簡(jiǎn)稱 入隊(duì) */
149 bool addQueue( Queue &Q, int x )
150 {
151 if ( isFull( Q ) == true ) // 檢測(cè)隊(duì)列是否以滿
152 {
153 return false;
154 }
155
156 int i;
157
158 for ( i = 0; i < maxSize; i++ )
159 {
160 if ( Q.data[i] == 0 ) // 當(dāng)為0時(shí)則表示此位置沒(méi)被復(fù)值,即可在此位置入隊(duì),且該值變?yōu)殛?duì)尾
161 {
162 if ( i == 0 ) // 設(shè)隊(duì)頭
163 {
164 Q.front = x;
165 }
166
167 Q.data[i] = x;
168
169 Q.rear = x; // 設(shè)隊(duì)尾,每添加一個(gè)值,則該值即為隊(duì)尾
170 return true;
171 }
172 }
173 }
174
175 /* 若隊(duì)列Q非空,則刪去Q的隊(duì)頭元素,并返回該元素. 此操作簡(jiǎn)稱 出隊(duì) */
176 bool delQueue( Queue &Q )
177 {
178 if ( isEmpty( Q ) == true ) // 檢測(cè)隊(duì)列是否為空
179 {
180 return false;
181 }
182
183 int i;
184
185 /* 刪除隊(duì)頭元素，并將所有隊(duì)列元素提前一個(gè)位置 */
186 for ( i = 0; i < maxSize; i++ )
187 {
188 if ( Q.data[i] == 0 || i == maxSize - 1 ) // 判斷隊(duì)列中元素是否以全部提前
189 {
190 Q.data[i] = 0;
191 Q.front = Q.data[0]; // 設(shè)隊(duì)頭,每出隊(duì)一個(gè)值,則原來(lái)第二個(gè)值變成隊(duì)頭
192 return true;
193 }
194
195 Q.data[i] = Q.data[i+1]; // 將隊(duì)列元素提前
196 }
197 }
198
199 /* 若隊(duì)列Q非空,則返回隊(duì)頭元素,但不改變隊(duì)列Q的狀態(tài). */
200 int queueFront( Queue &Q )
201 {
202 if ( isEmpty( Q ) == true ) // 檢測(cè)隊(duì)列是否為空
203 {
204 return false;
205 }
206
207 return Q.front; // 返回隊(duì)頭元素
208
209 }
210
211 /* 顯示隊(duì)列中的元素 */
212 bool queueDisplay( Queue &Q )
213 {
214 if ( isEmpty( Q ) == true ) // 檢測(cè)隊(duì)列是否為空
215 {
216 return false;
217 }
218
219 int i;
220
221 for ( i = 0; i < maxSize; i++ )
222 {
223 if ( Q.data[i] == 0 ) // 判斷隊(duì)列中元素是否以全部顯示
224 {
225 return true;
226 }
227
228 cout << "第" << i + 1 << "個(gè): " << Q.data[i] << endl;
229 }
230
231 }
本文來(lái)自CSDN博客，轉(zhuǎn)載出處：http://blog.csdn.net/dadalan/archive/2008/09/05/2883946.aspx