如需轉(zhuǎn)載, 請(qǐng)咨詢作者, 并且注明出處.
有任何問題, 可以關(guān)注我的微博: coderwhy, 或者添加我的微信: 372623326
棧也是一種非常常見的數(shù)據(jù)結(jié)構(gòu), 并且在程序中的應(yīng)用非常廣泛.
一. 認(rèn)識(shí)棧結(jié)構(gòu)
我們先來簡(jiǎn)單認(rèn)識(shí)一下棧結(jié)構(gòu), 它的特點(diǎn)和應(yīng)用場(chǎng)景等.
棧結(jié)構(gòu)
-
數(shù)組
- 我們知道數(shù)組是一種線性結(jié)構(gòu), 并且可以在數(shù)組的任意位置插入和刪除數(shù)據(jù).
- 但是有時(shí)候, 我們?yōu)榱藢?shí)現(xiàn)某些功能, 必須對(duì)這種任意性加以限制.
- 而棧和隊(duì)列就是比較常見的受限的線性結(jié)構(gòu), 我們先來學(xué)習(xí)棧結(jié)構(gòu).
-
棧(stack)账千,它是一種運(yùn)算受限的線性表,后進(jìn)先出(LIFO)
- LIFO(last in first out)表示就是后進(jìn)入的元素, 第一個(gè)彈出椊拿桑空間. 類似于自動(dòng)餐托盤, 最后放上的托盤, 往往先把拿出去使用.
- 其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算暗膜。這一端被稱為棧頂,相對(duì)地鞭衩,把另一端稱為棧底学搜。
- 向一個(gè)棧插入新元素又稱作進(jìn)棧、入椔垩埽或壓棧瑞佩,它是把新元素放到棧頂元素的上面,使之成為新的棧頂元素坯台;
- 從一個(gè)棧刪除元素又稱作出椌嫱瑁或退棧,它是把棧頂元素刪除掉蜒蕾,使其相鄰的元素成為新的棧頂元素稠炬。
-
生活中類似于棧的
- 自助餐的托盤, 最新放上去的, 最先被客人拿走使用.
- 收到很多的郵件(實(shí)體的), 從上往下依次處理這些郵件. (最新到的郵件, 最先處理)
- 注意: 不允許改變郵件的次序, 比如從最小開始, 或者處于最緊急的郵件, 否則就不再是棧結(jié)構(gòu)了. 而是隊(duì)列或者優(yōu)先級(jí)隊(duì)列結(jié)構(gòu).
-
棧結(jié)構(gòu)的圖解
img
-
程序中什么是使用棧實(shí)現(xiàn)的呢?
- 學(xué)了這么久的編程, 是否聽說過, 函數(shù)調(diào)用棧呢?
- 我們知道函數(shù)之間和相互調(diào)用: A調(diào)用B, B中又調(diào)用C, C中又調(diào)用D.
- 那樣在執(zhí)行的過程中, 會(huì)先將A壓入棧, A沒有執(zhí)行完, 所有不會(huì)彈出棧.
- 在A執(zhí)行的過程中調(diào)用了B, 會(huì)將B壓入到棧, 這個(gè)時(shí)候B在棧頂, A在棧底.
- 如果這個(gè)時(shí)候B可以執(zhí)行完, 那么B會(huì)彈出棧. 但是B有執(zhí)行完嗎? 沒有, 它調(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)用棧的稱呼, 就來自于它們內(nèi)部的實(shí)現(xiàn)機(jī)制. (通過棧來實(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)
我們來實(shí)現(xiàn)一個(gè)類, 用于模擬棧中的操作.
棧的創(chuàng)建
-
我們先來創(chuàng)建一個(gè)棧的類, 用于封裝棧相關(guān)的操作
// 棧類 function Stack() { // 棧中的屬性 var items = [] // 棧相關(guān)的方法 }
-
代碼解析:
- 我們創(chuàng)建了一個(gè)Stack構(gòu)造函數(shù), 用戶創(chuàng)建棧的類.
- 在構(gòu)造函數(shù)中, 定義了一個(gè)變量, 這個(gè)變量可以用于保存當(dāng)前棧對(duì)象中所有的元素.
- 這個(gè)變量是一個(gè)數(shù)組類型. 我們之后無論是壓棧操作還是出棧操作, 都是從數(shù)組中添加和刪除元素.
- 棧有一些相關(guān)的操作方法, 通常無論是什么語言, 操作都是比較類似的.
棧的操作
-
棧常見有哪些操作呢?
-
push(element)
: 添加一個(gè)新元素到棧頂位置. -
pop()
:移除棧頂?shù)脑兀瑫r(shí)返回被移除的元素咪啡。 -
peek()
:返回棧頂?shù)脑厥灼簦粚?duì)棧做任何修改(這個(gè)方法不會(huì)移除棧頂?shù)脑兀瑑H僅返回它)撤摸。 -
isEmpty()
:如果棧里沒有任何元素就返回true
毅桃,否則返回false
褒纲。 -
clear()
:移除棧里的所有元素。 -
size()
:返回棧里的元素個(gè)數(shù)钥飞。這個(gè)方法和數(shù)組的length
屬性很類似莺掠。
-
現(xiàn)在我們來實(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è)比較常見的方法, 主要目的是看一眼棧頂?shù)脑?
- 注意: 和pop不同, peek僅僅的瞥一眼棧頂?shù)脑? 并不需要將這個(gè)元素從棧頂彈出.
// peek操作 this.peek = function () { return items[items.length - 1] }
-
isEmpty方法
- isEmpty方法用戶判斷棧中是否有元素.
- 實(shí)現(xiàn)起來非常簡(jiǎn)單, 直接判斷數(shù)組中的元素個(gè)數(shù)是為0, 為0返回true, 否則返回false
// 判斷棧中的元素是否為空 this.isEmpty = function () { return items.length == 0 }
-
size方法
- size方法是獲取棧中元素的個(gè)數(shù).
- 因?yàn)槲覀兪褂玫氖菙?shù)組來作為棧的底層實(shí)現(xiàn)的, 所以直接獲取數(shù)組的長(zhǎng)度即可.(也可以使用鏈表作為棧的頂層實(shí)現(xiàn))
// 獲取棧中元素的個(gè)數(shù) this.size = function () { return items.length }
完整代碼
-
下面我們給出自定義棧的完整代碼:
- 注意: 這里我們?yōu)榱藢傩苑椒ǚ旁谝黄? 沒有使用原型來封裝方法.
// 棧類 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 } }
棧的使用
-
我們來使用封裝的棧, 模擬剛才的面試題
- 我們做了一下A, 其他大家可以自己練習(xí)一下.
- C是無法使用棧來模擬的, 因?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
類,現(xiàn)在就用它解決一些計(jì)算機(jī)科學(xué)中的問題读宙。
十進(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)。
- 沒有十進(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)制是滿二進(jìn)一)察纯,直到結(jié)果是0為止帕棉。
-
舉個(gè)例子,把十進(jìn)制的數(shù)字10轉(zhuǎn)化成二進(jìn)制的數(shù)字饼记,過程大概是這樣:
img
-
如果我們希望使用代碼來實(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))