原文：http://www.reibang.com/p/5d020c00fcb8
你還在為開(kāi)發(fā)中頻繁切換環(huán)境打包而煩惱嗎？快來(lái)試試 Environment Switcher 吧牲尺！使用它可以在app運(yùn)行時(shí)一鍵切換環(huán)境，而且還支持其他貼心小功能痕支，有了它媽媽再也不用擔(dān)心頻繁環(huán)境切換了焦读。https://github.com/CodeXiaoMai/EnvironmentSwitcher
上一章：程序猿必修課之?dāng)?shù)據(jù)結(jié)構(gòu)（七）棧2
隊(duì)列的定義
隊(duì)列（Queue）是只允許在一端進(jìn)行插入操作列赎，而在另一端進(jìn)行刪除操作的線性表。
隊(duì)列是一種先進(jìn)先出（First In First Out）的線性表馅而，簡(jiǎn)稱FIFO。允許插入的一端稱為隊(duì)尾譬圣，允許刪除的一端稱為隊(duì)頭瓮恭。
隊(duì)列的抽象數(shù)據(jù)類型
隊(duì)列是特殊的線性表，因此它的各種操作類似線性表胁镐，不同的是插入數(shù)據(jù)只能在隊(duì)尾進(jìn)行偎血，刪除數(shù)據(jù)只能在隊(duì)頭進(jìn)行。
ADT 隊(duì)列（Queue）
Data
同線性表盯漂。元素的類型相同颇玷，相鄰元素具有前驅(qū)和后繼關(guān)系。
Operation
initQueue(*Q): 隊(duì)列初始化就缆，建立一個(gè)空隊(duì)列帖渠。
destroyQueue(*Q): 若隊(duì)列 Q 存在，就銷毀它竭宰。
clearQueue(*Q): 將隊(duì)列清空空郊。
isEmpty(*Q): 若隊(duì)列為空，返回 true切揭；否則返回 false狞甚。
getHead(Q, *e): 若隊(duì)列 Q 存在且不為空，則用 e 返回隊(duì)列 Q 中的隊(duì)頭元素廓旬。
enQueue(*Q, e): 若隊(duì)列 Que 存在哼审，插入新元素 e 到隊(duì)列 Q 中并成為隊(duì)尾元素。
deQueue(*Q, *e): 刪除隊(duì)列 Q 中隊(duì)頭元素，并用 e 返回涩盾。
getLength(Q): 返回隊(duì)列 Q 的元素個(gè)數(shù)十气。
endADT
循環(huán)隊(duì)列
我們把頭尾相接的隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為循環(huán)隊(duì)列。
用 front 指針指向隊(duì)頭元素春霍，用 rear 指針指向隊(duì)尾元素的下一個(gè)位置（為了避免數(shù)組越界砸西，隊(duì)尾元素后要留一個(gè)空閑單元，保存 rear 指針）址儒。所以當(dāng) front == rear 時(shí)芹枷，表示隊(duì)列為空；當(dāng)數(shù)組中只有一個(gè)空閑單元時(shí)隊(duì)列就滿了离福。
因?yàn)槭茄h(huán)隊(duì)列杖狼，所以 rear 可能比 front 大，也可能比 fornt 小妖爷，如下圖所示：
可以看出蝶涩，它們可能只相差一個(gè)位置，但也可能相差整整一圈絮识。所以若隊(duì)列的最大容量為 queueSize绿聘，那么隊(duì)列滿的條件是：(rear + 1) % queueSize == front。
當(dāng) rear > front 時(shí)（即左圖）次舌，隊(duì)列的長(zhǎng)度為 rear - front熄攘；當(dāng) rear < front 時(shí)（即右圖），隊(duì)列的長(zhǎng)度由兩部分構(gòu)成彼念，一部分是 queueSize - front挪圾，另一部分是 0 + rear，所以隊(duì)列長(zhǎng)度為 rear - front + queueSize逐沙。所以通用的計(jì)算隊(duì)列長(zhǎng)度的公式為：
(rear - front + QueueSize) % queueSize
循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
define MAXSIZE 10
typedef struct {
int data[MAXSIZE];
int front;
int rear;
} Queue;
初始化：
void initQueue(Queue *q) {
q->front = 0;
q->rear = 0;
}
求隊(duì)列長(zhǎng)度
int queueLength(Queue q) {
return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}
入隊(duì)操作：
boolean enQueue(Queue *q, int e) {
/* 隊(duì)列已滿 */
if ((q->rear + 1) % MAXSIZE == q->front)
return false;
q->data[q->rear] = e;
q->rear = (q->rear + 1) % MAXSIZE;
return true;
}
出隊(duì)操作：
boolean deQueue(Queue *q, int *e) {
/* 隊(duì)列為空 */
if (q->front == q->rear)
return false;
*e = q->data[q->front];
q->front = (q->front + 1) % MAXSIZE;
return true;
}
雖然循環(huán)隊(duì)列解決了出隊(duì)時(shí)算法的時(shí)間復(fù)雜度不高的問(wèn)題哲思，但是它仍然有數(shù)組可能會(huì)溢出的問(wèn)題，所以還需要鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)解決這個(gè)問(wèn)題吩案。
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棚赔，其實(shí)就是線性表的單鏈表，只不過(guò)它只能尾進(jìn)頭出而已徘郭，簡(jiǎn)稱為鏈隊(duì)列靠益。
為了方便操作，隊(duì)頭指針指向鏈隊(duì)列的頭結(jié)點(diǎn)残揉；尾指針指向終端結(jié)點(diǎn)胧后。當(dāng) front 和 rear 都指向頭結(jié)點(diǎn)時(shí)，隊(duì)列為空抱环。
鏈隊(duì)列的結(jié)構(gòu)為：
typedef struct QNode {
int data;
struct QNode *next;
}QNode, *pQueue;
typedef struct{
pQueue front;
pQueue rear;
}LinkQueue;
入隊(duì)操作
boolean enQueue(LinkQueue *q, int e) {
pQueue s = (pQueue)malloc(sizeof(QNode));
if(!s)
return false;
s->data = e;
s->next = NULL;
q->rear->next = s;
q->rear = s;
return true;
}
出隊(duì)操作
出隊(duì)操作就是頭結(jié)點(diǎn)的后繼結(jié)點(diǎn) p 出隊(duì)绩卤，將頭結(jié)點(diǎn)的后繼改為 p 的后繼結(jié)點(diǎn)途样，如果p 是 rear 指向的結(jié)點(diǎn)，那么還要將 rear 指向頭結(jié)點(diǎn)濒憋。
boolean deQueue(LinkQueue *q, int *e) {
pQueue p;
if (q->front == q->rear)
return false;
p = q->front->next;
*e = p->data;
q->front->next = p->next;
if(q->rear == p)
q->rear = q->front;
free(p);
return true;
}
比較循環(huán)隊(duì)列和鏈隊(duì)列
從時(shí)間復(fù)雜度，它們的基本操作都是 O(1)陶夜；但是循環(huán)隊(duì)列需要先申請(qǐng)好空間凛驮，使用期間不釋放，而對(duì)于鏈隊(duì)列条辟，每次申請(qǐng)和釋放結(jié)點(diǎn)也會(huì)存在一些時(shí)間開(kāi)銷黔夭。
從空間上來(lái)說(shuō)，循環(huán)隊(duì)列必須有一個(gè)固定的長(zhǎng)度羽嫡，這樣就可能存在空間浪費(fèi)的問(wèn)題本姥；而鏈隊(duì)列不存在這個(gè)問(wèn)題，盡管它需要一個(gè)指針域杭棵。
總的來(lái)說(shuō)婚惫，在可以確定隊(duì)列長(zhǎng)度最大值的情況下，建議用循環(huán)隊(duì)列魂爪，反之用鏈隊(duì)列先舷。
