本文內(nèi)容取自于小甲魚的數(shù)據(jù)結構與算法虫啥。http://www.reibang.com/p/230e6fde9c75

1. 線性表

線性表（List）：由零個或多個數(shù)據(jù)元素組成的有限序列。

這里需要強調(diào)幾個關鍵的地方：

首先它是一個序列奄妨，也就是說元素之間是有個先來后到的涂籽。若元素存在多個，則第一個元素無前驅砸抛，而最后一個元素無后繼评雌，其他元素都有且只有一個前驅和后繼。另外直焙，線性表強調(diào)是有限的景东，事實上無論計算機發(fā)展到多強大，它所處理的元素都是有限的奔誓。

若將線性表記為（a1,…,ai-1,ai,ai+1,…an）,則表中ai-1領先于ai,ai領先于ai+1,稱ai-1是ai的直接前驅元素,ai+1是ai的直接后繼元素斤吐。

所以線性表元素的個數(shù)n(n>=0)定義為線性表的長度，當n=0時厨喂，稱為空表和措。

1.1 線性表之數(shù)組

1.1.1 操作

(1) 定義線性表

線性表存儲結構定義：

大家看到了蜕煌，這里我們封裝了一個結構斜纪，事實上就是對數(shù)組進行封裝彩届，增加了個當前長度的變量罷了歼冰。

總結下靡狞，順序存儲結構封裝需要三個屬性：

存儲空間的起始位置，數(shù)組data隔嫡，它的存儲位置就是線性表存儲空間的存儲位置甸怕。

線性表的最大存儲容量：數(shù)組的長度MaxSize。

線性表的當前長度：length腮恩。

注意梢杭，數(shù)組的長度與線性表的當前長度需要區(qū)分一下：

數(shù)組的長度是存放線性表的存儲空間的總長度，一般初始化后不變秸滴。

而線性表的當前長度是線性表中元素的個數(shù)武契，是會變化的。

(2) 獲取元素

實現(xiàn)GetElem的具體操作荡含，即將線性表L中的第i個位置元素值返回咒唆。就程序而言非常簡單了，我們只需要把數(shù)組第i-1下標的值返回即可释液。

(3) 插入元素

1. 如果插入位置不合理全释，拋出異常；

2. 如果線性表長度大于等于數(shù)組長度均澳，則拋出異澈蘖铮或動態(tài)增加數(shù)組容量符衔；

3. 從最后一個元素開始向前遍歷到第i個位置找前，分別將它們都向后移動一個位置；

4. 將要插入元素填入位置i處判族；

5. 線性表長+1躺盛。

(4) 刪除元素

1. 如果刪除位置不合理，拋出異常形帮；

2. 取出刪除元素槽惫；

3. 從刪除元素位置開始遍歷到最后一個元素位置周叮，分別將它們都向前移動一個位置；

4. 表長-1界斜。

1.1.2 優(yōu)缺點

線性表的順序存儲結構仿耽，在存、讀數(shù)據(jù)時各薇，不管是哪個位置项贺，時間復雜度都是O(1)。而在插入或刪除時峭判，時間復雜度都是O(n)开缎。這就說明，它比較適合元素個數(shù)比較穩(wěn)定林螃，不經(jīng)常插入和刪除元素奕删，而更多的操作是存取數(shù)據(jù)的應用。

(1) 優(yōu)點

無須為表示表中元素之間的邏輯關系而增加額外的存儲空間疗认。

可以快速地存取表中任意位置的元素完残。

(2) 缺點

插入和刪除操作需要移動大量元素。

當線性表長度變化較大時横漏，難以確定存儲空間的容量坏怪。

容易造成存儲空間的“碎片”。

1.2 線性表之鏈表

前面我們講的線性表的順序存儲結構绊茧，它最大的缺點就是插入和刪除時需要移動大量元素铝宵，這顯然就需要耗費時間。那我們能不能針對這個缺陷或者說遺憾提出解決的方法呢华畏？要解決這個問題鹏秋，我們就得考慮一下導致這個問題的原因！為什么當插入和刪除時亡笑，就要移動大量的元素侣夷？原因就在于相鄰兩元素的存儲位置也具有鄰居關系，它們在內(nèi)存中的位置是緊挨著的仑乌，中間沒有間隙百拓，當然就無法快速插入和刪除。

線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素晰甚，這組存儲單元可以存在內(nèi)存中未被占用的任意位置衙传。比起順序存儲結構每個數(shù)據(jù)元素只需要存儲一個位置就可以了。

1.2.1 單鏈表

現(xiàn)在鏈式存儲結構中厕九，除了要存儲數(shù)據(jù)元素信息外蓖捶，還要存儲它的后繼元素的存儲地址（指針）。也就是說除了存儲其本身的信息外扁远，還需存儲一個指示其直接后繼的存儲位置的信息俊鱼。我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域刻像，把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱為指針或鏈并闲。這兩部分信息組成數(shù)據(jù)元素稱為存儲映像细睡，稱為結點(Node)。n個結點鏈接成一個鏈表帝火，即為線性表(a1, a2, a3, …, an)的鏈式存儲結構纹冤。因為此鏈表的每個結點中只包含一個指針域，所以叫做單鏈表购公。

對于線性表來說萌京，總得有個頭有個尾，鏈表也不例外宏浩。我們把鏈表中的第一個結點的存儲位置叫做頭指針知残，最后一個結點指針為空(NULL)。

頭指針：

1. 頭指針是指鏈表指向第一個結點的指針比庄，若鏈表有頭結點求妹，則是指向頭結點的指針。

2. 頭指針具有標識作用佳窑，所以常用頭指針冠以鏈表的名字（指針變量的名字）制恍。

3. 無論鏈表是否為空，頭指針均不為空神凑。

4. 頭指針是鏈表的必要元素净神。

頭結點：

1. 頭結點是為了操作的統(tǒng)一和方便而設立的，放在第一個元素的結點之前溉委，其數(shù)據(jù)域一般無意義（但也可以用來存放鏈表的長度）鹃唯。

2. 有了頭結點蒿讥，對在第一元素結點前插入結點和刪除第一結點起操作與其它結點的操作就統(tǒng)一了滑臊。

3. 頭結點不一定是鏈表的必須要素。

1.2.1.1 操作

(1) 定義單鏈表

我們看到結點由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼結點地址的指針域組成挚赊。假設p是指向線性表第i個元素的指針藻三，則該結點ai的數(shù)據(jù)域我們可以用p->data的值是一個數(shù)據(jù)元素洪橘。結點ai的指針域可以用p->next來表示，p->next的值是一個指針棵帽。那么p->next指向誰呢熄求？當然指向第i+1個元素！也就是指向ai+1的指針岖寞。

問題：如果p->data = ai抡四，那么p->next->data = ?

答案：p->next->data = ai+1柜蜈。

(2) 讀取元素

在線性表的順序存儲結構中仗谆，我們要計算任意一個元素的存儲位置是很容易的指巡。但在單鏈表中，由于第i個元素到底在哪隶垮？我們壓根兒沒辦法一開始就知道藻雪，必須得從第一個結點開始挨個兒找。因此狸吞，對于單鏈表實現(xiàn)獲取第i個元素的數(shù)據(jù)的操作GetElem勉耀，在算法上相對要麻煩一些。

1. 聲明一個結點p指向鏈表第一個結點蹋偏，初始化j從1開始便斥；

2. 當j<i, 就遍歷鏈表，讓p的指針向后移動威始，不斷指向下一個結點枢纠，j+1

3. 若到鏈表末尾p為空，則說明第i個元素不存在黎棠；

4. 否則查找成功晋渺，返回結點p的數(shù)據(jù)。

(3) 插入元素

我們先來看下單鏈表的插入脓斩。假設存儲元素e的結點為s木西，要實現(xiàn)結點p、p->next和s之間邏輯關系的變化随静，大家參考下圖思考一下：

我們思考后發(fā)覺根本用不著驚動其他結點八千，只需要讓s->next和p->next的指針做一點改變。

s->next = p->next;

p->next = s;

我們通過圖片來解讀一下這兩句代碼燎猛。

那么我們考慮一下大部分初學者最容易搞壞腦子的問題：這兩句代碼的順序可不可以交換過來叼丑？先 p->next = s;再 s->next = p->next;

大家發(fā)現(xiàn)沒有？如果先執(zhí)行p->next的話會先被覆蓋為s的地址扛门，那么s->next = p->next其實就等于s->next = s了鸠信。所以這兩句是無論如何不能弄反的，這點初學者一定要注意咯~

思路：

1. 聲明一結點p指向鏈表頭結點论寨，初始化j從1開始星立；

2. 當j<1時，就遍歷鏈表葬凳，讓p的指針向后移動绰垂，不斷指向下一結點，j累加1火焰；

3. 若到鏈表末尾p為空劲装，則說明第i個元素不存在；

4. 否則查找成功，在系統(tǒng)中生成一個空結點s占业；

5. 將數(shù)據(jù)元素e賦值給s->data绒怨；

6. 單鏈表的插入剛才兩個標準語句；

7. 返回成功谦疾。

(4) 刪除元素

現(xiàn)在我們再來看單鏈表的刪除操作南蹂。

假設元素a2的結點為q，要實現(xiàn)結點q刪除單鏈表的操作念恍，其實就是將它的前繼結點的指針繞過指向后繼結點即可六剥。那我們所要做的，實際上就是一步：

可以這樣：p->next = p->next->next; 也可以是：q=p->next; p->next=q->next峰伙。

思路：

1. 聲明結點p指向鏈表第一個結點疗疟，初始化j=1；

2. 當j<1時瞳氓，就遍歷鏈表秃嗜，讓P的指針向后移動，不斷指向下一個結點顿膨，j累加1锅锨；

3. 若到鏈表末尾p為空，則說明第i個元素不存在恋沃；

4. 否則查找成功必搞，將欲刪除結點p->next賦值給q；

5. 單鏈表的刪除標準語句p->next = q->next囊咏；

6. 將q結點中的數(shù)據(jù)賦值給e恕洲，作為返回；

7. 釋放q結點梅割。

1.2.1.2 單鏈表的整表建立

對于順序存儲結構的線性表的整表創(chuàng)建霜第，我們可以用數(shù)組的初始化來直觀理解。

而單鏈表和順序存儲結構就不一樣了户辞，它不像順序存儲結構數(shù)據(jù)這么集中泌类，它的數(shù)據(jù)可以是分散在內(nèi)存各個角落的，他的增長也是動態(tài)的底燎。對于每個鏈表來說刃榨，它所占用空間的大小和位置是不需要預先分配劃定的，可以根據(jù)系統(tǒng)的情況和實際的需求即時生成双仍。

創(chuàng)建單鏈表的過程是一個動態(tài)生成鏈表的過程枢希，從“空表”的初始狀態(tài)起，依次建立各元素結點并逐個插入鏈表朱沃。

思路：

1. 聲明一結點p和計數(shù)器變量i苞轿；

2. 初始化一空鏈表L茅诱；

3. 讓L的頭結點的指針指向NULL，即建立一個帶頭結點的單鏈表搬卒；

4. 循環(huán)實現(xiàn)后繼結點的賦值和插入瑟俭。

(1) 頭插法建立

頭插法從一個空表開始，生成新結點秀睛，讀取數(shù)據(jù)存放到新結點的數(shù)據(jù)域中尔当，然后將新結點插入到當前鏈表的表頭上莲祸，直到結束為止蹂安。簡單來說，就是把新加進的元素放在表頭后的第一個位置：先讓新節(jié)點的next指向頭節(jié)點之后锐帜，然后讓表頭的next指向新節(jié)點田盈。

(2) 尾插法建立

頭插法建立鏈表雖然算法簡單，但生成的鏈表中結點的次序和輸入的順序相反缴阎。就像現(xiàn)實社會我們鄙視插隊不遵守紀律的孩子允瞧，那編程中我們也可以不這么干，我們可以把思維逆過來：把新結點都插入到最后蛮拔，這種算法稱之為尾插法述暂。

1.2.1.3 單鏈表的整表刪除

當我們不打算使用這個單鏈表時，我們需要把它銷毀（真狠建炫，不要就給別人嘛畦韭，還銷毀~）。

其實也就是在內(nèi)存中將它釋放掉肛跌，以便于留出空間給其他程序或軟件使用艺配。

思路：

1. 聲明結點p和q；

2. 將第一個結點賦值給p衍慎，下一結點賦值給q转唉；

3. 循環(huán)執(zhí)行釋放p和將q賦值給p的操作；

這段算法代碼里稳捆，常見的錯誤就是有同學會覺得q變量沒有存在的必要赠法，只需要在循環(huán)體內(nèi)直接寫free(p); p = p->next; 即可？

可這個世上沒有無緣無故的愛乔夯，這樣做會帶來什么問題呢期虾？

要知道p是一個結點，它除了有數(shù)據(jù)域驯嘱，還有指針域镶苞。當我們做free(p);時候，其實是對它整個結點進行刪除和內(nèi)存釋放的工作鞠评。而我們整表刪除

是需要一個個結點刪除的茂蚓，所以我們就需要q來記載p的下一個結點。

1.2.1.4 優(yōu)缺點

我們分別從存儲分配方式、時間性能聋涨、空間性能三方面來做對比晾浴。

(1) 存儲分配方式

順序存儲結構用一段連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。

單鏈表采用鏈式存儲結構牍白，用一組任意的存儲單元存放線性表的元素脊凰。

(2) 時間性能

查找:?順序存儲結構O(1), 單鏈表O(n)

插入和刪除:

順序存儲結構需要平均移動表長一半的元素，時間為O(n)

單鏈表在計算出某位置的指針后茂腥，插入和刪除時間僅為O(1)

(3) 空間性能

順序存儲結構需要預分配存儲空間狸涌，分大了，容易造成空間浪費最岗，分小了帕胆，容易發(fā)生溢出。

單鏈表不需要分配存儲空間般渡，只要有就可以分配懒豹，元素個數(shù)也不受限制。

總而言之驯用，

若線性表需要頻繁查找脸秽，很少進行插入和刪除操作時，宜采用順序存儲結構蝴乔。

若需要頻繁插入和刪除時记餐，宜采用單鏈表結構。

比如說游戲開發(fā)中淘这，對于用戶注冊的個人信息剥扣，除了注冊時插入數(shù)據(jù)外，絕大多數(shù)情況都是讀取铝穷，所以應該考慮用順序存儲結構钠怯。

而游戲中的玩家的武器或者裝備列表，隨著玩家的游戲過程中曙聂，可能會隨時增加或刪除晦炊，此時再用順序存儲就不太合適了，單鏈表結構就可以大展拳腳了宁脊。

當線性表中的元素個數(shù)變化較大或者根本不知道有多大時断国，最好用單鏈表結構，這樣可以不需要考慮存儲空間的大小問題榆苞。

而如果事先知道線性表的大致長度稳衬，比如一年12個月，一周就是星期一至星期日共七天坐漏，這種用順序存儲結構效率會高很多薄疚。

1.2.2 靜態(tài)鏈表

用數(shù)組描述的鏈表叫做靜態(tài)鏈表碧信，這種描述方法叫做游標實現(xiàn)法。

1.2.2.1 定義靜態(tài)鏈表

我們對數(shù)組的第一個和最后一個元素做特殊處理街夭，他們的data不存放數(shù)據(jù)砰碴。我們通常把未使用的數(shù)組元素稱為備用鏈表。數(shù)組的第一個元素板丽，即下標為0的那個元素的cur就存放備用鏈表的第一個結點的下標呈枉。數(shù)組的最后一個元素，即下標為MAXSIZE-1的cur則存放第一個有數(shù)值的元素的下標埃碱，相當于單鏈表中的頭結點作用猖辫。

1.2.2.2 插入

1.2.2.3 刪除

回收空閑游標。

1.2.2.4 優(yōu)缺點

優(yōu)點：

在插入和刪除操作時乃正，只需要修改游標住册，不需要移動元素婶博，從而改進了在順序存儲結構中的插入和刪除操作需要移動大量元素的缺點瓮具。

缺點：

沒有解決連續(xù)存儲分配（數(shù)組）帶來的表長難以確定的問題。

失去了順序存儲結構隨機存取的特性凡人。

總的來說名党，靜態(tài)鏈表其實是為了給沒有指針的編程語言設計的一種實現(xiàn)單鏈表功能的方法。

盡管我們可以用單鏈表就不用靜態(tài)鏈表了挠轴，但這樣的思考方式是非常巧妙的传睹，應該理解其思想，以備不時之需岸晦。

1.2.2.5 單鏈表面試題

題目：快速找到未知長度單鏈表的中間節(jié)點欧啤。

既然是面試題就一定有普通方法和高級方法。

普通的方法很簡單启上，首先遍歷一遍單鏈表以確定單鏈表的長度L邢隧。然后再次從頭節(jié)點出發(fā)循環(huán)L/2次找到單鏈表的中間節(jié)點。

算法復雜度為：O(L+L/2)=O(3L/2)冈在。

高級的方法：利用快慢指針倒慧！

利用快慢指針原理：設置兩個指針*search、*mid都指向單鏈表的頭節(jié)點包券。其中* search的移動速度是*mid的2倍纫谅。當*search指向末尾節(jié)點的時候，mid正好就在中間了溅固。這也是標尺的思想付秕。

1.2.3 循環(huán)鏈表

對于單鏈表，由于每個結點只存儲了向后的指針侍郭，到了尾部標識就停止了向后鏈的操作询吴。也就是說俩垃，按照這樣的方式，只能索引后繼結點不能索引前驅結點汰寓。這會帶來什么問題呢口柳？例如不從頭結點出發(fā)，就無法訪問到全部結點有滑。

事實上要解決這個問題也并不麻煩跃闹，只需要將單鏈表中終端結點的指針端由空指針改為指向頭結點，問題就結了毛好。將單鏈表中終端結點的指針端由空指針改為指向頭結點望艺，就使整個單鏈表形成一個環(huán)，這種頭尾相接的單鏈表成為單循環(huán)鏈表肌访，簡稱循環(huán)鏈表找默。

注：這里并不是說循環(huán)鏈表一定要有頭結點。

其實循環(huán)鏈表的單鏈表的主要差異就在于循環(huán)的判斷空鏈表的條件上吼驶，原來判斷head->next是否為null惩激，現(xiàn)在則是head->next是否等于head⌒费荩回到剛才的問題风钻，由于終端結點用尾指針rear指示，則查找終端結點是O(1)酒请，而開始結點是rear->next->next骡技，當然也是O(1)。

1.2.3 帶環(huán)單鏈表

有環(huán)的定義是羞反，鏈表的尾節(jié)點指向了鏈表中的某個節(jié)點布朦。

那么要判斷單鏈表中是否有環(huán)，主要有以下兩種方法：

方法一：使用p昼窗、q兩個指針是趴，p總是向前走，但q每次都從頭開始走膏秫，對于每個節(jié)點右遭，看p走的步數(shù)是否和q一樣。如圖缤削，當p從6走到3時窘哈，用了6步，此時若q從head出發(fā)亭敢，則只需兩步就到3滚婉，因而步數(shù)不等，出現(xiàn)矛盾帅刀，存在環(huán)让腹。

方法二：使用p远剩、q兩個指針，p每次向前走一步骇窍，q每次向前走兩步瓜晤，若在某個時候p == q，則存在環(huán)腹纳。

1.2.4 雙向鏈表

大家都知道痢掠，任何事物出現(xiàn)的初期都顯得有些不完善。例如我們的火車剛發(fā)明的時候是只有一個“頭”的嘲恍，所以如果它走的線路是如下：

A->B->C->D->E->F->G->H->I->J->K->L->A

假設這會兒火車正停在K處呢足画，要他送一批貨到J處，那么它將走的路線是：

K->L->A->B->C->D->E->F->G->H->I->J

嗯佃牛，所以后來我們的火車就都有兩個頭了淹辞。看完這個例子俘侠，大家就明白雙向鏈表的必要性了吧象缀。

1.2.4.1 建立雙向鏈表

1.2.4.2 插入

1.2.4.3 刪除

1.2.4 雙向循環(huán)鏈表

2. 棧

官方定義：棧（Stack）是一個后進先出（Last in first out,LIFO）的線性表，它要求只在表尾進行刪除和插入操作兼贡。

小甲魚定義：所謂的棧攻冷，其實也就是一個特殊的線性表（順序表娃胆、鏈表）遍希，但是它在操作上有一些特殊的要求和限制：棧的元素必須“后進先出”。棧的操作只能在這個線性表的表尾進行里烦。

注：對于棧來說凿蒜，這個表尾稱為棧的棧頂（top），相應的表頭稱為棧底（bottom）胁黑。

棧的插入操作（Push）废封，叫做進棧，也稱為壓棧丧蘸，入棧漂洋。類似子彈放入彈夾的動作。

棧的刪除操作（Pop）力喷，叫做出棧刽漂，也稱為彈棧。如同彈夾中的子彈出夾弟孟。

2.1 棧的順序存儲結構

因為棧的本質(zhì)是一個線性表贝咙，線性表有兩種存儲形式，那么棧也有分為棧的順序存儲結構和棧的鏈式存儲結構拂募。最開始棧中不含有任何數(shù)據(jù)庭猩，叫做空棧窟她，此時棧頂就是棧底。然后數(shù)據(jù)從棧頂進入蔼水，棧頂棧底分離震糖，整個棧的當前容量變大。數(shù)據(jù)出棧時從棧頂彈出趴腋，棧頂下移试伙，整個棧的當前容量變小。

入棧操作:?入棧操作又叫壓棧操作于样，就是向棧中存放數(shù)據(jù)疏叨。

入棧操作要在棧頂進行，每次向棧中壓入一個數(shù)據(jù)穿剖，top指針就要+1蚤蔓，知道棧滿為止。

出棧操作:?出棧操作就是在棧頂取出數(shù)據(jù)糊余，棧頂指針隨之下移的操作秀又。

每當從棧內(nèi)彈出一個數(shù)據(jù)，棧的當前容量就-1贬芥。

2.1.1 清空棧

所謂清空一個棧吐辙，就是將棧中的元素全部作廢，但棧本身物理空間并不發(fā)生改變（不是銷毀）蘸劈。因此我們只要將s->top的內(nèi)容賦值為s->base即可昏苏，這樣s->base等于s->top，也就表明這個棧是空的了威沫。這個原理跟高級格式化一樣只是但單純地清空文件列表而沒有覆蓋硬盤的原理是一樣的贤惯。

2.1.2 銷毀棧

銷毀一個棧與清空一個棧不同，銷毀一個棧是要釋放掉該棧所占據(jù)的物理內(nèi)存空間棒掠，因此不要把銷毀一個棧與清空一個棧這兩種操作混淆孵构。

2.1.3 計算棧的當前容量

計算棧的當前容量也就是計算棧中元素的個數(shù)，因此只要返回s.top-s.base即可烟很。

注意颈墅，棧的最大容量是指該棧占據(jù)內(nèi)存空間的大小，其值是s.stackSize雾袱，它與棧的當前容量不是一個概念哦恤筛。

2.2 棧的鏈式存儲結構

現(xiàn)在我們來看下棧的鏈式存儲結構，簡稱棧鏈谜酒。（通常我們用的都是棧的順序存儲結構存儲叹俏，鏈式存儲我們作為一個知識點，大家知道就好Ｆё濉）

棧因為只是棧頂來做插入和刪除操作粘驰，所以比較好的方法就是將棧頂放在單鏈表的頭部屡谐，棧頂指針和單鏈表的頭指針合二為一。

2.2.1 建立棧

2.2.2 進棧

2.2.3 出棧

3. 隊列

隊列（queue）是只允許在一端進行插入操作蝌数，而在另一端進行刪除操作的線性表愕掏。

與棧相反，隊列是一種先進先出（First In First Out, FIFO）的線性表顶伞。

與棧相同的是饵撑，隊列也是一種重要的線性結構，實現(xiàn)一個隊列同樣需要順序表或鏈表作為基礎唆貌。

3.1 隊列的鏈式存儲結構

隊列既可以用鏈表實現(xiàn)滑潘，也可以用順序表實現(xiàn)。跟棧相反的是锨咙，棧一般我們用順序表來實現(xiàn)语卤，而隊列我們常用鏈表來實現(xiàn)，簡稱為鏈隊列酪刀。

3.1.1 建立隊列

我們將隊頭指針指向鏈隊列的頭結點粹舵，而隊尾指針指向終端結點。（注：頭結點不是必要的骂倘，但為了方便操作眼滤，我們加上了。）

空隊列時历涝，front和rear都指向頭結點诅需。

3.1.2 入隊列

3.1.3 出隊列

出隊列操作是將隊列中的第一個元素移出，隊頭指針不發(fā)生改變睬关，改變頭結點的next指針即可诱担。出隊列的操作過程如下：

如果原隊列只有一個元素，那么我們就應該處理一下隊尾指針电爹。

3.1.4 銷毀隊列

由于鏈隊列建立在內(nèi)存的動態(tài)區(qū)，因此當一個隊列不再有用時應當把它及時銷毀掉料睛，以免過多地占用內(nèi)存空間丐箩。

3.2 隊列的順序存儲結構

我們先按照應有的思路來考慮下如何構造隊列的順序存儲結構，然后發(fā)掘都遇到了什么麻煩恤煞。

我們假設一個隊列有n個元素屎勘，則順序存儲的隊列需建立一個大于n的存儲單元，并把隊列的所有元素存儲在數(shù)組的前n個單元居扒，數(shù)組下標為0的一端則是隊頭概漱。

入隊列操作其實就是在隊尾追加一個元素，不需要任何移動喜喂，時間復雜度為O(1)瓤摧。

出隊列則不同竿裂，因為我們已經(jīng)架設下標為0的位置是隊列的隊頭，因此每次出隊列操作所有元素都要向前移動照弥。

在現(xiàn)實中也是如此腻异，一群人在排隊買火車票，前邊的人買好了離開拯腮，后面的人就要全部向前一步補上空位咱士』ど蓿可是我們研究數(shù)據(jù)結構和算法的一個根本目的就是要想方設法提高我們的程序的效率，按剛才的方式机打，出隊列的時間復雜度是O(n)，效率大打折扣片迅！

如果我們不去限制隊頭一定要在下標為0的位置姐帚，那么出隊列的操作就不需要移動全體元素。

但是這樣也會出現(xiàn)一些問題障涯，例如按下邊的情形繼續(xù)入隊列罐旗，就會出現(xiàn)數(shù)組越界的錯誤。

3.2.1 循環(huán)隊列

要解決假溢出的辦法就是如果后面滿了唯蝶，就再從頭開始九秀，也就是頭尾相接的循環(huán)。

循環(huán)隊列它的容量是固定的粘我，并且它的隊頭和隊尾指針都可以隨著元素入出隊列而發(fā)生改變鼓蜒，這樣循環(huán)隊列邏輯上就好像是一個環(huán)形存儲空間。但要注意的是征字，在實際的內(nèi)存當中都弹，不可能有真正的環(huán)形存儲區(qū)，我們只是用順序表模擬出來的邏輯上的循環(huán)匙姜。

于是我們發(fā)覺了畅厢，似乎循環(huán)隊列的實現(xiàn)只需要靈活改變front和rear指針即可。

也就是讓front或rear指針不斷加1氮昧，即時超出了地址范圍框杜，也會自動從頭開始。我們可以采取取模運算處理：

(rear+1) % QueueSize

(front+1) % QueueSize

取模就是取余數(shù)的意思袖肥，他取到的值永遠不會大于除數(shù)咪辱。

3.2.1.1 定義循環(huán)隊列

3.2.1.2 入隊列

3.2.1.3 出隊列