1. 棧的定義
棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行
結(jié)論：后進(jìn)先出（Last In First Out），簡(jiǎn)稱(chēng)為L(zhǎng)IFO線性表。結(jié)論：后進(jìn)先出（Last In First Out），簡(jiǎn)稱(chēng)為L(zhǎng)IFO線性表。
棧的基本運(yùn)算有六種：
構(gòu)造空棧：InitStack(S)、
判棧空: StackEmpty(S)、
判棧滿：?StackFull(S)、
進(jìn)棧：?Push(S,x)、可形象地理解為壓入，這時(shí)棧中會(huì)多一個(gè)元素
退棧：?Pop(S) 、 可形象地理解為彈出，彈出后棧中就無(wú)此元素了。
取棧頂元素：StackTop(S),不同與彈出，只是使用棧頂元素的值，該元素仍在棧頂不會(huì)改變。
由于棧也是線性表，因此線性表的存儲(chǔ)結(jié)構(gòu)對(duì)棧也適用，通常棧有順序棧和鏈棧兩種存儲(chǔ)結(jié)構(gòu)，這兩種存儲(chǔ)結(jié)構(gòu)的不同，則使得實(shí)現(xiàn)棧的基本運(yùn)算的算法也有所不同。
我們要了解的是，在順序棧中有"上溢"和"下溢"的概念。順序棧好比一個(gè)盒子，我們?cè)诶镱^放了一疊書(shū)，當(dāng)我們要用書(shū)的話只能從第一本開(kāi)始拿(你會(huì)把盒子翻過(guò)來(lái)嗎?真聰明^^)，那么當(dāng)我們把書(shū)本放到這個(gè)棧中超過(guò)盒子的頂部時(shí)就放不下了(疊上去的不算，哼哼)，這時(shí)就是"上溢","上溢"也就是棧頂指針指出棧的外面，顯然是出錯(cuò)了。反之，當(dāng)棧中已沒(méi)有書(shū)時(shí)，我們?cè)偃ツ?，看看沒(méi)書(shū)，把盒子拎起來(lái)看看盒底，還是沒(méi)有，這就是"下溢"。"下溢"本身可以表示棧為空棧,因此可以用它來(lái)作為控制轉(zhuǎn)移的條件。
鏈棧則沒(méi)有上溢的限制，它就象是一條一頭固定的鏈子，可以在活動(dòng)的一頭自由地增加鏈環(huán)(結(jié)點(diǎn))而不會(huì)溢出，鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要在頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。
棧的基本運(yùn)算有六種：
構(gòu)造空棧：InitStack(S)、
判?？? StackEmpty(S)、
判棧滿：?StackFull(S)、
進(jìn)棧：?Push(S,x)、可形象地理解為壓入，這時(shí)棧中會(huì)多一個(gè)元素
退棧：?Pop(S) 、 可形象地理解為彈出，彈出后棧中就無(wú)此元素了。
取棧頂元素：StackTop(S),不同與彈出，只是使用棧頂元素的值，該元素仍在棧頂不會(huì)改變。
由于棧也是線性表，因此線性表的存儲(chǔ)結(jié)構(gòu)對(duì)棧也適用，通常棧有順序棧和鏈棧兩種存儲(chǔ)結(jié)構(gòu)，這兩種存儲(chǔ)結(jié)構(gòu)的不同，則使得實(shí)現(xiàn)棧的基本運(yùn)算的算法也有所不同。
我們要了解的是，在順序棧中有"上溢"和"下溢"的概念。順序棧好比一個(gè)盒子，我們?cè)诶镱^放了一疊書(shū)，當(dāng)我們要用書(shū)的話只能從第一本開(kāi)始拿(你會(huì)把盒子翻過(guò)來(lái)嗎?真聰明^^)，那么當(dāng)我們把書(shū)本放到這個(gè)棧中超過(guò)盒子的頂部時(shí)就放不下了(疊上去的不算，哼哼)，這時(shí)就是"上溢","上溢"也就是棧頂指針指出棧的外面，顯然是出錯(cuò)了。反之，當(dāng)棧中已沒(méi)有書(shū)時(shí)，我們?cè)偃ツ茫纯礇](méi)書(shū)，把盒子拎起來(lái)看看盒底，還是沒(méi)有，這就是"下溢"。"下溢"本身可以表示棧為空棧,因此可以用它來(lái)作為控制轉(zhuǎn)移的條件。
鏈棧則沒(méi)有上溢的限制，它就象是一條一頭固定的鏈子，可以在活動(dòng)的一頭自由地增加鏈環(huán)(結(jié)點(diǎn))而不會(huì)溢出，鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要在頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。
2.1 隊(duì)列定義
隊(duì)列(Queue)也是一種運(yùn)算受限的線性表，它的運(yùn)算限制與棧不同，是兩頭都有限制，插入只能在表的一端進(jìn)行(只進(jìn)不出)，而刪除只能在表的另一端進(jìn)行(只出不進(jìn))，允許刪除的一端稱(chēng)為隊(duì)尾(rear)，允許插入的一端稱(chēng)為隊(duì)頭?(Front)
,隊(duì)列的操作原則是先進(jìn)先出的，所以隊(duì)列又稱(chēng)作FIFO表(First In First Out)
隊(duì)列的基本運(yùn)算也有六種：
置空隊(duì) ：InitQueue(Q)
判隊(duì)空：?QueueEmpty(Q)
判隊(duì)滿：?QueueFull(Q)
入隊(duì) ：?EnQueue(Q,x)
出隊(duì) ：?DeQueue(Q)
取隊(duì)頭元素：?QueueFront(Q),不同與出隊(duì)，隊(duì)頭元素仍然保留。
隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)，前者稱(chēng)順序隊(duì)列，后者為鏈隊(duì)。
對(duì)于順序隊(duì)列，我們要理解"假上溢"的現(xiàn)象。
我們現(xiàn)實(shí)中的隊(duì)列比如人群排隊(duì)買(mǎi)票，隊(duì)伍中的人是可以一邊進(jìn)去從另一頭出來(lái)的，除非地方不夠，總不會(huì)有"溢出"的現(xiàn)象，相似地，當(dāng)隊(duì)列中元素完全充滿這個(gè)向量空間時(shí)，再入隊(duì)自然就會(huì)上溢，如果隊(duì)列中已沒(méi)有元素，那么再要出隊(duì)也會(huì)下溢。
那么"假上溢"就是怎么回事呢?
因?yàn)樵谶@里，我們的隊(duì)列是存儲(chǔ)在一個(gè)向量空間里，在這一段連續(xù)的存儲(chǔ)空間中，由一個(gè)隊(duì)列頭指針和一個(gè)尾指針表示這個(gè)隊(duì)列，當(dāng)頭指針和尾指針指向同一個(gè)位置時(shí)，隊(duì)列為空，也就是說(shuō)，隊(duì)列是由兩個(gè)指針中間的元素構(gòu)成的。在隊(duì)列中，入隊(duì)和出隊(duì)并不是象現(xiàn)實(shí)中，元素一個(gè)個(gè)地向前移動(dòng)，走完了就沒(méi)有了,而是指針在移動(dòng)，當(dāng)出隊(duì)操作時(shí)，頭指針向前(即向量空間的尾部)增加一個(gè)位置，入隊(duì)時(shí)，尾指針向前增加一個(gè)位置，在某種情況下，比如說(shuō)進(jìn)一個(gè)出一個(gè)，兩個(gè)指針就不停地向前移動(dòng)，直到隊(duì)列所在向量空間的尾部，這時(shí)再入隊(duì)的話，尾指針就要跑到向量空間外面去了，僅管這時(shí)整個(gè)向量空間是空的，隊(duì)列也是空的，卻產(chǎn)生了"上溢"現(xiàn)象，這就是假上溢。
為了克服這種現(xiàn)象造成的空間浪費(fèi)，我們引入循環(huán)向量的概念，就好比是把向量空間彎起來(lái)，形成一個(gè)頭尾相接的環(huán)形，這樣，當(dāng)存于其中的隊(duì)列頭尾指針移到向量空間的上界(尾部)時(shí)，再加1的操作(入隊(duì)或出隊(duì))就使指針指向向量的下界，也就是從頭開(kāi)始。這時(shí)的隊(duì)列就稱(chēng)循環(huán)隊(duì)列。
通常我們應(yīng)用的大都是循環(huán)隊(duì)列。由于循環(huán)的原因，光看頭尾指針重疊在一起我們并不能判斷隊(duì)列是空的還是滿的，這時(shí)就需要處理一些邊界條件，以區(qū)別隊(duì)列是空還是滿。方法至少有三種，一種是另設(shè)一個(gè)布爾變量來(lái)判斷(就是請(qǐng)別人看著，是空還是滿由他說(shuō)了算)，第二種是少用一個(gè)元素空間，當(dāng)入隊(duì)時(shí)，先測(cè)試入隊(duì)后尾指針是不是會(huì)等于頭指針，如果相等就算隊(duì)已滿，不許入隊(duì)。第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)，這樣就可以隨時(shí)知道隊(duì)列的長(zhǎng)度了，只要隊(duì)列中的元素個(gè)數(shù)等于向量空間的長(zhǎng)度，就是隊(duì)滿。
2.2 隊(duì)列的順序存儲(chǔ)
３．棧和隊(duì)列的實(shí)現(xiàn)：.pop, .push, .shift和 .unshift
每個(gè)人都知道.push可以再數(shù)組末尾添加元素，但是你知道可以使用[].push(‘a(chǎn)’, ‘b’, ‘c’, ‘d’, ‘z’)一次性添加多個(gè)元素嗎?
.pop 方法是.push 的反操作，它返回被刪除的數(shù)組末尾元素。如果數(shù)組為空，將返回void 0 (undefined),使用.pop和.push可以創(chuàng)建LIFO (last in first out)棧。
01functionStack () {
02this._stack = []
03}
04Stack.prototype.next =function() {
05returnthis._stack.pop()
06}
07Stack.prototype.add =function() {
08returnthis._stack.push.apply(this._stack, arguments)
09}
10stack =newStack()
11stack.add(1,2,3)
12stack.next()
13// <- 3
14相反，可以使用.shift和 .unshift創(chuàng)建FIFO (firstinfirst out)隊(duì)列。
15
16functionQueue () {
17this._queue = []
18}
19Queue.prototype.next =function() {
20returnthis._queue.shift()
21}
22Queue.prototype.add =function() {
23returnthis._queue.unshift.apply(this._queue, arguments)
24}
25queue =newQueue()
26queue.add(1,2,3)
27queue.next()
28// <- 1
29Using .shift (or .pop) is an easy way to loop through a set of array elements,whiledraining the arrayinthe process.
30list = [1,2,3,4,5,6,7,8,9,10]
31while(item = list.shift()) {
32console.log(item)
33}
34list
35// <- []
