我們在使用手機(jī)的時候束亏，偶爾都會碰到過卡住的時候铃在，比如一個地方怎么點都沒有用，屏幕也卡住不顯示其他東西碍遍，但當(dāng)你把卡住的App關(guān)閉掉之后定铜，手機(jī)的操作顯示就又恢復(fù)正常了，其實這就是因為操作系統(tǒng)中的各個程序的指令堆積在一起排隊執(zhí)行怕敬，而某一個App卡住的時候揣炕，大家都卡住了。
操作系統(tǒng)中是應(yīng)用了一種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)剛才提到的先到先執(zhí)行的排隊功能东跪，這就是隊列畸陡。
隊列的定義
隊列是一種只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表虽填。
隊列是一種先進(jìn)先出（First In First Out）的線性表丁恭，簡稱FIFO。允許插入的一端為隊尾斋日，允許刪除的一端稱為隊頭牲览。假設(shè)隊列 q = (q1,q2,q3,....qn)，那么我們一般定義q1就是隊頭恶守，而qn自然為隊尾了第献。這樣我們在刪除操作時，就從q1開始兔港，而插入操作時則從qn開始庸毫。這也比較符合我們的生活習(xí)慣，我們在排隊的時候押框，就是先到的人先出列岔绸，而晚到的人就在隊尾排隊理逊。
循環(huán)隊列
以前的文章橡伞，我寫了線性表有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)盒揉，而同樣，隊列作為一種特殊的線性表兑徘，自然也存在這兩種存儲方式刚盈。首先我們先來看隊列的順序存儲結(jié)構(gòu)。
隊列順序存儲結(jié)構(gòu)的不足
和線性表的順序存儲結(jié)構(gòu)的缺點一樣挂脑，隊列的若是采用常規(guī)的順序存儲結(jié)構(gòu)藕漱，那么它在插入和刪除時，每個元素都要依次向前或向后移動位置崭闲，此時的時間復(fù)雜度為O(n)肋联。而當(dāng)隊列中隊頭之前的位置空出來，而隊尾的元素已滿時刁俭，明明在隊頭之前可能還有空間橄仍，但是按照順序存儲結(jié)構(gòu)的判斷，此時已經(jīng)不能插入數(shù)據(jù)牍戚，再插入數(shù)據(jù)的話侮繁，整個數(shù)組就會溢出，而這種之前有空位如孝，卻插入到后面溢出位置的做法宪哩，我們稱為 假溢出 。
循環(huán)隊列的定義
所以為了解決這種假溢出的辦法就是后面滿了第晰，就再從頭開始锁孟，尋找之前空出來的空間，把數(shù)據(jù)存儲進(jìn)去但荤，也就是頭尾相接的循環(huán)罗岖。我們把隊列這種頭尾相接的順序存儲結(jié)構(gòu)稱為循環(huán)隊列。
循環(huán)隊列的順序存儲結(jié)構(gòu)代碼如下：
#define MAXSIZE 10 //循環(huán)隊列的最大存儲空間
/**
* 函數(shù)運(yùn)行狀態(tài)代碼
*/
#define SUCCESS 1
#define ERROR 0
typedef int Status ; //函數(shù)的運(yùn)行狀態(tài) 假設(shè)為int類型
typedef int QElemType; //QElemType的類型根據(jù)實際情況而定腹躁，這里假設(shè)為int
/**
* 定義一個循環(huán)隊列
*/
typedef struct{
QElemType data[MAXSIZE];
int front; //循環(huán)隊列的頭指針
int rear; //循環(huán)隊列的尾指針
}sqQueue;
循環(huán)隊列的初始化代碼如下:
/**
* 初始化一個循環(huán)隊列
*
* @param Q 循環(huán)隊列的線性表
*
* @return Status
*/
Status InitQueue (sqQueue *Q)
{
Q->front = 0;
Q->rear = 0;
return SUCCESS;
}
我們來實現(xiàn)求一個循環(huán)隊列的長度的功能桑包，其實很簡單，只要返回尾指針與頭指針相減的數(shù)據(jù)就可以,當(dāng)然纺非，這里我們要考慮當(dāng)循環(huán)了一遍之后頭尾交換位置的情況
/**
* 求循環(huán)隊列的隊列長度
*
* @param Q 循環(huán)隊列的線性表
*
* @return length
*/
int QueueLength (sqQueue Q)
{
return (Q.rear - Q.front +MAXSIZE) %MAXSIZE;
}
跟線性表一樣哑了，我們一般要完成插入和刪除功能的代碼，而實現(xiàn)部分如下:
循環(huán)隊列的入隊列操作代碼:
/**
* 循環(huán)隊列的入隊操作
*
* @param Q 循環(huán)隊列的線性表
* @param e 將要插入的數(shù)據(jù)
*
* @return Sataus
*/
Status EnQueue (sqQueue * Q ,QElemType e)
{
if ((Q->rear + 1) %MAXSIZE == Q->front) { //判斷隊列是否滿
return ERROR;
}
Q->data[Q->rear] = e; //將元素e賦值給隊尾
Q->rear = (Q->rear + 1) %MAXSIZE; //將rear尾指針后移一位
//若到隊尾則轉(zhuǎn)到數(shù)組頭部
return SUCCESS;
}
循環(huán)隊列的出隊列的操作代碼 :
/**
* 循環(huán)隊列的出隊列操作
*
* @param Q 循環(huán)隊列的線性表
* @param e 存儲隊頭數(shù)據(jù)的元素
*
* @return Status
*/
Status DeQueue (sqQueue * Q, QElemType *e)
{
if (Q->front == Q->rear) { //判斷隊列是否為空
return ERROR;
}
*e = Q->data[Q->front]; //將隊頭元素賦值給e
Q->front = (Q->front + 1) %MAXSIZE; //front指針后移一位
return SUCCESS;
}
從上面的代碼烧颖，我們能夠分析出弱左，單是順序存儲，若不是循環(huán)隊列炕淮，算法的時間性能是不高的拆火，但是循環(huán)隊列又面臨著數(shù)組可能會溢出的問題，所以我們還需要研究一下不需要擔(dān)心隊列長度的鏈?zhǔn)酱鎯Y(jié)構(gòu)。
隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)
隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)们镜，其實就是線性表的單鏈表币叹，只不過它只能尾進(jìn)頭出而已，我們把它簡稱為鏈隊列模狭。為了操作上的方便颈抚，我們將隊列的頭指針指向鏈隊列的頭結(jié)點，而尾指針指向終點結(jié)點嚼鹉。
空隊列時贩汉，front和rear都指向頭結(jié)點。
鏈隊列的結(jié)構(gòu)為:
/**
* 結(jié)點結(jié)構(gòu)
*/
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
/**
* 隊列的鏈表結(jié)構(gòu)
*/
typedef struct
{
QueuePtr front, rear; //隊頭隊尾指針
}LinkQueue;
鏈隊列的入隊操作:
/**
* 插入元素e為鏈隊列的新的隊尾元素
*
* @param Q 鏈隊列
* @param e 將要插入的元素e
*
* @return Status
*/
Status EnLinkQueue (LinkQueue * Q, QElemType e)
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
if (!s) { //存儲分配失敗
return ERROR;
}
s->data = e;
s->next = NULL;
Q->rear->next = s; //把擁有元素e的新節(jié)點s賦值給原隊尾結(jié)點的后繼
Q->rear = s; //把當(dāng)前的s設(shè)置為隊尾的結(jié)點锚赤，rear指向s
return SUCCESS;
}
鏈隊列的出隊操作匹舞，其實就是頭結(jié)點的后繼結(jié)點出隊，將頭結(jié)點的后繼改成它后面的結(jié)點线脚，之后再釋放要刪除元素的內(nèi)存策菜，若鏈表除了頭結(jié)點之外只剩下一個元素時，則要將rear指向頭結(jié)點酒贬。
/**
* 若隊列不空又憨，刪除鏈隊列的隊頭元素，并用e返回其值
*
* @param Q 鏈隊列
* @param e 刪除的元素的數(shù)據(jù)
*
* @return Status
*/
Status DeLinkeQueue (LinkQueue *Q, QElemType *e)
{
QueuePtr p;
if (Q->front == Q->rear) {
return ERROR;
}
p = Q->front->next; //將欲刪除的隊頭結(jié)點暫存給p
*e = p->data; //將欲刪除的隊頭結(jié)點賦值給e
Q->front->next = p->next; //將原隊頭的結(jié)點后繼p->next賦值給隊頭結(jié)點的后繼
if (Q->rear == p) { //若隊頭是隊尾锭吨，則刪除后繼后將rear指向頭結(jié)點
Q->rear = Q->front;
}
free(p); //釋放p
return SUCCESS;
}
循環(huán)隊列和鏈隊列的比較
循環(huán)隊列和鏈隊列的比較可以從兩個方面來比較蠢莺，首先從時間上，其實它們的基本操作都是常數(shù)時間零如，時間復(fù)雜度都為O(1)躏将，不過循環(huán)隊列是事先申請好空間的，而鏈隊列是即時申請空間的所以鏈隊列的每次申請和釋放操作都會帶來一定的性能消耗和時間開銷考蕾。
從空間上來說祸憋，循環(huán)隊列必須有一個固定的長度，所以就有了存儲元素個數(shù)和空間的浪費(fèi)的問題肖卧，而鏈隊列則不存在這個問題蚯窥。
總得來說，在可以確定隊列長度最大值的情況下塞帐，建議用循環(huán)隊列拦赠，如果你無法預(yù)估隊列的長度時，則用鏈隊列葵姥。
總結(jié)
我們在這里的總結(jié)荷鼠，將棧和隊列拿來比較。
- 棧（stack）是限定進(jìn)在表尾進(jìn)行插入和刪除操作的線性表
- 隊列（Queue）是只允許在一端進(jìn)行插入操作榔幸，而在另一端進(jìn)行刪除操作的線性表允乐。
他們均可以用線性表的順序存儲結(jié)構(gòu)來實現(xiàn)矮嫉，但都存在著順序存儲的一些弊端，因此它們各自有各自的技巧來解決這個問題牍疏。
對于棧來說敞临，如果存儲的數(shù)據(jù)類型相同的棧，則可以用數(shù)組的兩端作棧底的方法來讓兩個棧共享數(shù)據(jù)麸澜，這就可以最大化的利用數(shù)組的空間。
對于隊列來說奏黑，為了避免數(shù)組插入和刪除時需要移動數(shù)據(jù)炊邦，于是就引入了循環(huán)隊列，使得隊頭和隊尾可以在數(shù)組中循環(huán)變化熟史。解決了移動數(shù)據(jù)的時間損耗馁害，使得本來插入和刪除的時間復(fù)雜度從O(n)變成了O(1)。
它們也都可以通過鏈?zhǔn)酱鎯Y(jié)構(gòu)來實現(xiàn)蹂匹，實現(xiàn)原則上與線性表基本相同碘菜。
