棧

棧是最簡單的數據結構，也是最重要的數據結構。它的原則就是後進先出（LIFO），棧被使用於非常多的地方，例如瀏覽器中的後退按鈕，文本編輯器中的撤銷機制，接下來我們用Python來具體實現這個數據結構。

Python實現

棧中的方法

作為一個棧（用S來表示），最基本的方法有下麵幾個：

• S.push(e): 將元素e添加到S的棧頂

• S.pop(): 從棧S中移除並返回棧頂的元素，如果此時棧是空的，那麼這個操作將會報錯

• S.top(): 不移除棧頂元素，但返回棧頂元素，如果此時棧是空的，那麼這個操作將會報錯

• S.is_empty(): 如果棧為空，則返回True，否則返回False

• len(S): 返回棧中元素的數量，使用len的特殊方法實現

具體實現

Python中的list類與棧的結構很像，但是又有許多不同之處，所以我們以list為基礎創建一個新的棧類,代碼如下：

class Stack():
    """
    以list為基礎實現的棧
    """

    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)

    def is_empty(self):
        return len(self._data) == 0

    def push(self, e):
        self._data.append(e)

    def pop(self):
        if self.is_empty():
            raise Empty('Stack is empty')
        return self._data.pop()

    def top(self):
        if self.is_empty():
            raise Empty('Stack is empty')
        return self._data[-1]

其中pop與top方法中對於空棧時報的異常是我們自定義的：

class Empty(Exception):

    pass

因為列表對於這種情況會產生IndexError，但這個異常與棧並不是很符合，所以我們使用了自定義的異常

簡單分析

由於Python是一門動態語言，與一些其他的語言相比，棧中的元素類型可以不一樣，所以棧在Python中的使用很靈活，但也有可能會因此使程式理解起來更複雜，如果想要實現這種要求嚴格的棧類型，可以使用基於array模塊中的緊湊數組實現

我們棧中的push方法是利用列表中的append方式實現的，那麼列表中的這種動態增加長度的方式我們是有必要瞭解一下的，先看一個例子：

import sys
data = []
for _ in range(30):
    a = len(data)
    b = sys.getsizeof(data)
    print('長度：{0:3d}; 占用位元組：{1:4d}'.format(a,b))
    data.append(None)

運行結果為：

長度： 0; 占用位元組： 64
長度： 1; 占用位元組： 96
長度： 2; 占用位元組： 96
長度： 3; 占用位元組： 96
長度： 4; 占用位元組： 96
長度： 5; 占用位元組： 128
長度： 6; 占用位元組： 128
長度： 7; 占用位元組： 128
長度： 8; 占用位元組： 128
長度： 9; 占用位元組： 192
長度： 10; 占用位元組： 192
長度： 11; 占用位元組： 192
長度： 12; 占用位元組： 192
長度： 13; 占用位元組： 192
長度： 14; 占用位元組： 192
長度： 15; 占用位元組： 192
長度： 16; 占用位元組： 192
長度： 17; 占用位元組： 264
長度： 18; 占用位元組： 264
長度： 19; 占用位元組： 264
長度： 20; 占用位元組： 264
長度： 21; 占用位元組： 264
長度： 22; 占用位元組： 264
長度： 23; 占用位元組： 264
長度： 24; 占用位元組： 264
長度： 25; 占用位元組： 264
長度： 26; 占用位元組： 344
長度： 27; 占用位元組： 344
長度： 28; 占用位元組： 344
長度： 29; 占用位元組： 344

通過觀察data列表占用位元組大小的增長規律，發現在不斷的添加中，data的占用的位元組每次增加的是越來越大。這是由於list在底層還是基於數組實現的，它每次都會先申請一個長度，當占用的位元組要超過最大範圍時，再將數組的大小增加。

很明顯，當不得不在底層增加數組長度的時候，這時的消耗必然比只添加數據時要大，所以在某些情況下，我們的棧的實現，可以增加一個設置固定長度，提前將所有位置初始化為None，那麼在程式運行時，就會減少了再增大底層數組時的開銷，這樣做有時會非常有用。

參考《數據結構與演算法Python語言實現》