數(shù)據(jù)結(jié)構(gòu)(三)之棧結(jié)構(gòu)

如需轉(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))
    
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末香伴,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子具则,更是在濱河造成了極大的恐慌即纲,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,378評(píng)論 6 516
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件博肋,死亡現(xiàn)場(chǎng)離奇詭異低斋,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)匪凡,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,970評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門膊畴,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人病游,你說我怎么就攤上這事唇跨。” “怎么了衬衬?”我有些...
    開封第一講書人閱讀 168,983評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵买猖,是天一觀的道長(zhǎng)。 經(jīng)常有香客問我佣耐,道長(zhǎng)政勃,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 59,938評(píng)論 1 299
  • 正文 為了忘掉前任兼砖,我火速辦了婚禮奸远,結(jié)果婚禮上既棺,老公的妹妹穿的比我還像新娘。我一直安慰自己懒叛,他們只是感情好丸冕,可當(dāng)我...
    茶點(diǎn)故事閱讀 68,955評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著薛窥,像睡著了一般胖烛。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上诅迷,一...
    開封第一講書人閱讀 52,549評(píng)論 1 312
  • 那天佩番,我揣著相機(jī)與錄音,去河邊找鬼罢杉。 笑死趟畏,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的滩租。 我是一名探鬼主播赋秀,決...
    沈念sama閱讀 41,063評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼律想!你這毒婦竟也來了猎莲?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,991評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤技即,失蹤者是張志新(化名)和其女友劉穎著洼,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體姥份,經(jīng)...
    沈念sama閱讀 46,522評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡郭脂,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,604評(píng)論 3 342
  • 正文 我和宋清朗相戀三年年碘,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了澈歉。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,742評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡屿衅,死狀恐怖埃难,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情涤久,我是刑警寧澤涡尘,帶...
    沈念sama閱讀 36,413評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站响迂,受9級(jí)特大地震影響考抄,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜蔗彤,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,094評(píng)論 3 335
  • 文/蒙蒙 一川梅、第九天 我趴在偏房一處隱蔽的房頂上張望疯兼。 院中可真熱鬧,春花似錦贫途、人聲如沸吧彪。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,572評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽姨裸。三九已至,卻和暖如春怨酝,著一層夾襖步出監(jiān)牢的瞬間傀缩,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,671評(píng)論 1 274
  • 我被黑心中介騙來泰國打工农猬, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留扑毡,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,159評(píng)論 3 378
  • 正文 我出身青樓盛险,卻偏偏與公主長(zhǎng)得像瞄摊,于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子苦掘,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,747評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容