如需轉(zhuǎn)載, 請(qǐng)咨詢(xún)作者, 并且注明出處.
有任何問(wèn)題, 可以關(guān)注我的微博: coderwhy, 或者添加我的微信: 372623326
棧也是一種非常常見(jiàn)的數(shù)據(jù)結(jié)構(gòu), 并且在程序中的應(yīng)用非常廣泛.
一. 認(rèn)識(shí)棧結(jié)構(gòu)
我們先來(lái)簡(jiǎn)單認(rèn)識(shí)一下棧結(jié)構(gòu), 它的特點(diǎn)和應(yīng)用場(chǎng)景等.
棧結(jié)構(gòu)
-
數(shù)組
- 我們知道數(shù)組是一種線(xiàn)性結(jié)構(gòu), 并且可以在數(shù)組的任意位置插入和刪除數(shù)據(jù).
- 但是有時(shí)候, 我們?yōu)榱藢?shí)現(xiàn)某些功能, 必須對(duì)這種任意性加以限制.
- 而棧和隊(duì)列就是比較常見(jiàn)的受限的線(xiàn)性結(jié)構(gòu), 我們先來(lái)學(xué)習(xí)棧結(jié)構(gòu).
-
棧（stack），它是一種運(yùn)算受限的線(xiàn)性表,后進(jìn)先出(LIFO)
- LIFO(last in first out)表示就是后進(jìn)入的元素, 第一個(gè)彈出棧空間. 類(lèi)似于自動(dòng)餐托盤(pán), 最后放上的托盤(pán), 往往先把拿出去使用.
- 其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。這一端被稱(chēng)為棧頂，相對(duì)地，把另一端稱(chēng)為棧底。
- 向一個(gè)棧插入新元素又稱(chēng)作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；
- 從一個(gè)棧刪除元素又稱(chēng)作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
-
生活中類(lèi)似于棧的
- 自助餐的托盤(pán), 最新放上去的, 最先被客人拿走使用.
- 收到很多的郵件(實(shí)體的), 從上往下依次處理這些郵件. (最新到的郵件, 最先處理)
- 注意: 不允許改變郵件的次序, 比如從最小開(kāi)始, 或者處于最緊急的郵件, 否則就不再是棧結(jié)構(gòu)了. 而是隊(duì)列或者優(yōu)先級(jí)隊(duì)列結(jié)構(gòu).
-
棧結(jié)構(gòu)的圖解
img
-
程序中什么是使用棧實(shí)現(xiàn)的呢?
- 學(xué)了這么久的編程, 是否聽(tīng)說(shuō)過(guò), 函數(shù)調(diào)用棧呢?
- 我們知道函數(shù)之間和相互調(diào)用: A調(diào)用B, B中又調(diào)用C, C中又調(diào)用D.
- 那樣在執(zhí)行的過(guò)程中, 會(huì)先將A壓入棧, A沒(méi)有執(zhí)行完, 所有不會(huì)彈出棧.
- 在A(yíng)執(zhí)行的過(guò)程中調(diào)用了B, 會(huì)將B壓入到棧, 這個(gè)時(shí)候B在棧頂, A在棧底.
- 如果這個(gè)時(shí)候B可以執(zhí)行完, 那么B會(huì)彈出棧. 但是B有執(zhí)行完嗎? 沒(méi)有, 它調(diào)用了C.
- 所以C會(huì)壓棧, 并且在棧頂. 而C調(diào)用了D, D會(huì)壓入到棧頂.
- 所以當(dāng)前的棧順序是: 棧頂A->B->C->D棧頂
- D執(zhí)行完, 彈出棧. C/B/A依次彈出棧.
- 所以我們有函數(shù)調(diào)用棧的稱(chēng)呼, 就來(lái)自于它們內(nèi)部的實(shí)現(xiàn)機(jī)制. (通過(guò)棧來(lái)實(shí)現(xiàn)的)
-
函數(shù)調(diào)用棧圖解:
img
棧面試題
-
面試題目:
img -
題目答案: C
- A答案: 65進(jìn)棧, 5出棧, 4進(jìn)棧出棧, 3進(jìn)棧出棧, 6出棧, 21進(jìn)棧,1出棧, 2出棧
- B答案: 654進(jìn)棧, 4出棧, 5出棧, 3進(jìn)棧出棧, 2進(jìn)棧出棧, 1進(jìn)棧出棧, 6出棧
- D答案: 65432進(jìn)棧, 2出棧, 3出棧, 4出棧, 1進(jìn)棧出棧, 5出棧, 6出棧
二. 棧結(jié)構(gòu)實(shí)現(xiàn)
我們來(lái)實(shí)現(xiàn)一個(gè)類(lèi), 用于模擬棧中的操作.
棧的創(chuàng)建
-
我們先來(lái)創(chuàng)建一個(gè)棧的類(lèi), 用于封裝棧相關(guān)的操作
// 棧類(lèi) function Stack() { // 棧中的屬性 var items = [] // 棧相關(guān)的方法 } -
代碼解析:
- 我們創(chuàng)建了一個(gè)Stack構(gòu)造函數(shù), 用戶(hù)創(chuàng)建棧的類(lèi).
- 在構(gòu)造函數(shù)中, 定義了一個(gè)變量, 這個(gè)變量可以用于保存當(dāng)前棧對(duì)象中所有的元素.
- 這個(gè)變量是一個(gè)數(shù)組類(lèi)型. 我們之后無(wú)論是壓棧操作還是出棧操作, 都是從數(shù)組中添加和刪除元素.
- 棧有一些相關(guān)的操作方法, 通常無(wú)論是什么語(yǔ)言, 操作都是比較類(lèi)似的.
棧的操作
-
棧常見(jiàn)有哪些操作呢?
-
push(element): 添加一個(gè)新元素到棧頂位置. -
pop()：移除棧頂?shù)脑兀瑫r(shí)返回被移除的元素。 -
peek()：返回棧頂?shù)脑?，不?duì)棧做任何修改（這個(gè)方法不會(huì)移除棧頂?shù)脑兀瑑H僅返回它）。 -
isEmpty()：如果棧里沒(méi)有任何元素就返回true，否則返回false。 -
clear()：移除棧里的所有元素。 -
size()：返回棧里的元素個(gè)數(shù)。這個(gè)方法和數(shù)組的length屬性很類(lèi)似。
-
現(xiàn)在我們來(lái)實(shí)現(xiàn)這些方法:
-
push方法
- 注意: 我們的實(shí)現(xiàn)是將最新的元素放在了數(shù)組的末尾, 那么數(shù)組末尾的元素就是我們的棧頂元素
// 壓棧操作 this.push = function (element) { items.push(element) } -
pop方法
- 注意: 出棧操作應(yīng)該是將棧頂?shù)脑貏h除, 并且返回.
- 因此, 我們這里直接從數(shù)組中刪除最后一個(gè)元素, 并且將該元素返回就可以了
// 出棧操作 this.pop = function (element) { return items.pop() } -
peek方法
- peek方法是一個(gè)比較常見(jiàn)的方法, 主要目的是看一眼棧頂?shù)脑?
- 注意: 和pop不同, peek僅僅的瞥一眼棧頂?shù)脑? 并不需要將這個(gè)元素從棧頂彈出.
// peek操作 this.peek = function () { return items[items.length - 1] } -
isEmpty方法
- isEmpty方法用戶(hù)判斷棧中是否有元素.
- 實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單, 直接判斷數(shù)組中的元素個(gè)數(shù)是為0, 為0返回true, 否則返回false
// 判斷棧中的元素是否為空 this.isEmpty = function () { return items.length == 0 } -
size方法
- size方法是獲取棧中元素的個(gè)數(shù).
- 因?yàn)槲覀兪褂玫氖菙?shù)組來(lái)作為棧的底層實(shí)現(xiàn)的, 所以直接獲取數(shù)組的長(zhǎng)度即可.(也可以使用鏈表作為棧的頂層實(shí)現(xiàn))
// 獲取棧中元素的個(gè)數(shù) this.size = function () { return items.length }
完整代碼
-
下面我們給出自定義棧的完整代碼:
- 注意: 這里我們?yōu)榱藢傩苑椒ǚ旁谝黄? 沒(méi)有使用原型來(lái)封裝方法.
// 棧類(lèi) function Stack() { // 棧中的屬性 var items = [] // 棧相關(guān)的方法 // 壓棧操作 this.push = function (element) { items.push(element) } // 出棧操作 this.pop = function () { return items.pop() } // peek操作 this.peek = function () { return items[items.length - 1] } // 判斷棧中的元素是否為空 this.isEmpty = function () { return items.length == 0 } // 獲取棧中元素的個(gè)數(shù) this.size = function () { return items.length } }
棧的使用
-
我們來(lái)使用封裝的棧, 模擬剛才的面試題
- 我們做了一下A, 其他大家可以自己練習(xí)一下.
- C是無(wú)法使用棧來(lái)模擬的, 因?yàn)椴徽_的是C
// 模擬面試題 var stack = new Stack() // 情況下代碼模擬 stack.push(6) stack.push(5) stack.pop() // 5 stack.push(4) stack.pop() // 4 stack.push(3) stack.pop() // 3 stack.pop() // 6 stack.push(2) stack.push(1) stack.pop() // 1 stack.pop() // 2
三. 棧結(jié)構(gòu)應(yīng)用
我們已經(jīng)學(xué)會(huì)了如何使用
Stack類(lèi)，現(xiàn)在就用它解決一些計(jì)算機(jī)科學(xué)中的問(wèn)題。
十進(jìn)制轉(zhuǎn)二進(jìn)制
-
為什么需要十進(jìn)制轉(zhuǎn)二進(jìn)制?
- 現(xiàn)實(shí)生活中，我們主要使用十進(jìn)制。
- 但在計(jì)算科學(xué)中，二進(jìn)制非常重要，因?yàn)橛?jì)算機(jī)里的所有內(nèi)容都是用二進(jìn)制數(shù)字表示的（0和1）。
- 沒(méi)有十進(jìn)制和二進(jìn)制相互轉(zhuǎn)化的能力，與計(jì)算機(jī)交流就很困難。
-
如何實(shí)現(xiàn)十進(jìn)制轉(zhuǎn)二進(jìn)制?
要把十進(jìn)制轉(zhuǎn)化成二進(jìn)制，我們可以將該十進(jìn)制數(shù)字和2整除（二進(jìn)制是滿(mǎn)二進(jìn)一），直到結(jié)果是0為止。
-
舉個(gè)例子，把十進(jìn)制的數(shù)字10轉(zhuǎn)化成二進(jìn)制的數(shù)字，過(guò)程大概是這樣：
img
-
如果我們希望使用代碼來(lái)實(shí)現(xiàn)這個(gè)功能呢?
// 封裝十進(jìn)制轉(zhuǎn)二進(jìn)制的函數(shù) function dec2bin(decNumer) { // 定義變量 var stack = new Stack() var remainder; // 循環(huán)除法 while (decNumer > 0) { remainder = decNumer % 2 decNumer = Math.floor(decNumer / 2) stack.push(remainder) } // 將數(shù)據(jù)取出 var binayriStrng = "" while (!stack.isEmpty()) { binayriStrng += stack.pop() } return binayriStrng } -
測(cè)試代碼:
// 測(cè)試函數(shù) alert(dec2bin(10)) alert(dec2bin(233)) alert(dec2bin(1000))
