<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                ### 6.5.2 堆棧 堆棧(stack)也是一種數據集合體,其中的數據構成一種具有“后進先出(LIFO)”性 質的數據結構,即最后加入堆棧的數據總是首先取出。現實中堆棧的例子俯拾皆是,例如碗櫥里的一摞碗、紙箱里的一摞書、彈夾中的子彈等等(圖 6.10),他們共同的特點是先放進 去的東西墊底,最后放進去的東西在頂上,而取東西的順序正好相反。 ![](https://box.kancloud.cn/2016-02-22_56cafce31b248.png) 圖 6.10 現實中的堆棧例子 如果忽略各種具體堆棧中無關緊要的成分,如所堆放的東西(碗、書、子彈)、容器(紙箱、碗櫥、彈夾)和放入/取出的具體實現(人工、機械),那么我們可以抽象地定義堆棧。 所謂堆棧,是以如下兩個操作進行處理的數據結構: + push(x):在堆棧頂部推入一個新數據 x,x 即成為新的棧頂元素; + pop():從堆棧中取出棧頂元素,顯然被取出的元素只能是最后加入堆棧的元素。 為了完善這兩個操作,還需提供一些輔助操作,如: + isFull():檢查堆棧是否已滿。如果堆棧具有固定大小,那么滿了之后是無法執行 push()的; + isEmpty():檢查堆棧是否為空。如果堆棧是空的,那么 pop()操作將出錯。 此前介紹的數據類型大多是具體的,即它們的實現方式是給定的,例如 int 類型是以 4 個字節來表示,字符串類型是特定編碼的字節串等等。而現在我們所討論的堆棧則是抽象數 據類型,因為我們只規定了堆棧的操作方式,并沒有規定操作的具體實現方式。 在具體應用中,可以采用多種不同的方式來實現堆棧這個抽象數據類型。例如,可以采 用列表來實現堆棧。令列表 stack 是存放數據的堆棧,按照堆棧的要求,對 stack 只能執行 push 和 pop 操作,不能像列表那樣可以隨機存取任何一個元素。假設以列表頭為棧底,以 列表尾為棧頂,那么向堆棧中放入元素就只能在尾部添加,Python 列表對象提供的 append 方法正好提供堆棧所需的功能,因此可以用 append 來實現 push(),形如: ``` def push(stack,x): stack.append(x) ``` 另外,Python 列表對象的 pop()方法的功能是取出列表的最后一個元素,恰好符合堆棧的 pop()方法的要求,因此可以這樣實現堆棧 pop 操作: ``` def pop(stack): return stack.pop() ``` 為了防止從空堆棧中取數據的錯誤,我們定義一個檢測堆棧是否為空的函數: ``` def isEmpty(stack): return (stack == []) ``` 利用上述以列表實現堆棧的技術,程序 6.5 首先通過用戶輸入數據創建一個堆棧,然后 再逐個取出堆棧成員。輸出恰好是輸入的逆序,這是由堆棧的 LIFO 性質決定的。可見,利 用堆棧來逆序顯示列表數據是非常容易的。 【程序 6.5】stack.py ``` def push(stack,x): stack.append(x) def pop(stack): return stack.pop() def isEmpty(stack): return (stack == []) def main(): stack = [] print "Pushing..." x = raw_input("Enter a string: ") while x != "": push(stack,x) x = raw_input("Enter a string: ") print "Popping..." while not isEmpty(stack): print pop(stack), main() ``` 下面是程序 6.5 的一次執行情況: ``` Pushing... Enter a string: 1st Enter a string: 2nd Enter a string: 3rd Enter a string: 4th Enter a string: Popping... 4th 3rd 2nd 1st ``` 堆棧在計算機科學中非常有用,一個常見的用例是實現表達式的計算。 讀者都熟悉算術表達式的中綴形式,但在用計算機處理表達式時常將表達式寫成后綴形式,例如“1 + 2”可寫成“1 2 +”、“3 + 4 * 5”可寫成“3 4 5 * +”。后綴形式的表達式可以 利用堆棧來非常方便地求值,算法如下: 1\. 掃描后綴形式的表達式,每次讀一個符號(運算數或者運算符); 2\. 如果讀到的是運算數,則 push 到堆棧中;如果讀到的是運算符,則從堆棧 pop 兩個運算 數,并執行該運算,然后將運算結果 push 入堆棧; 3\. 重復 1、2,直至到達表達式尾。這時堆棧中應該只剩一個運算數,就是表達式的結果值。 圖 6.11 顯示的是“3 4 5 * +”的計算過程。 ![](https://box.kancloud.cn/2016-02-22_56cafce334c11.png) 圖 6.11 利用堆棧對后綴表達式求值 以上求值部分非常容易實現,但要想對用戶輸入的中綴形式的算術表達式進行求值,還 需要先對輸入進行語法分析,拆分出運算符和運算數,然后改成后綴形式。這部分編程有點 復雜,所以在此我們就不實現這個程序了。有興趣的讀者可以嘗試解決這個問題。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看