棧

棧這個詞實際上在計算機科學里使用很多，除了數據結構外，還有內存里的棧區 （和堆對應），熟悉 C 系語言的話應該不會陌生。
上一章我們講到了先進先出 queue，其實用 python 的內置類型 collections.deque 或者我們自己實現的 LinkedList 來實現它都很簡單。
本章我們講講 后進先出的棧。

生活中的數據結構：

• 棧。好比在桶里頭放盤子，先放的盤子放在了底下，后來的盤子放在上邊。你要拿的時候，也是先拿最上邊的。

棧其實也很簡單，因為基礎操作就倆，一個 push 和一個 pop，咦，咋和隊列一樣的？
確實方法名字一樣，但是得到的結果可是不同的。

棧 ADT

上一章我介紹了我們怎樣選取恰到的數據結構來實現新的 ADT？你能想到這里我們應該使用之前提到的哪個數據結構來實現嗎？
你的大腦可能開始高(gui)速(su)旋轉了，上幾章學過的 array, list, deque, LinkedList, CircularDoubleLinkedList, queue
等在大腦里呼嘯而過，這個時候可能已經一臉愁容了，到底該選啥？

還用問嘛，當然是時間復雜度最小的啦，大部分情況下空間都是夠用的。
其實你會發現棧比隊列還簡單，因為它只在頂上操作（想象裝著盤子的桶），如果有一種數據結構能方便在尾部增減元素不就滿足需求了嗎。
這個時候如果你忘記了，可以翻翻前幾章，看看哪個數據結構符合要求。

想一下，似乎 CircularDoubleLinkedList 循環雙端隊列是滿足的，因為增刪最后一個元素都是 O(1)。
不過看了下示例代碼，似乎沒有 pop() 方法，對，因為我已經把實現 deque 作為思考題了。😂
如果之前你沒寫出來也沒關系，這里我們會再實現它。

視頻里我們將借助 CircularDoubleLinkedList 實現 雙端隊列 Deque ，并且用 Deque 實現 Stack。

Stack over flow 什么鬼？

嗯，stackoverflow 不是一個程序員問答網站嗎？沒錯。
函數的臨時變量是存儲在棧區的，如果你不幸寫了一個沒有出口的遞歸函數，就會這個錯。不信你試試：

def infinite_fib(n):return infinite_fib(n-1) + infinite_fib(n-2)
infinite_fib(10)

一大段輸出之后就會出現異常： RecursionError: maximum recursion depth exceeded。
后邊會講到遞歸，遞歸是初學者比較難理解的概念，在樹的遍歷等地方還會看到它。

源碼

# -*- coding: utf-8 -*-# NOTE: 這里拷貝的 double_link_list.py 里的代碼from collections import dequeclass Node(object):def __init__(self, value=None, prev=None, next=None):self.value, self.prev, self.next = value, prev, nextclass CircularDoubleLinkedList(object):"""循環雙端鏈表 ADT多了個循環其實就是把 root 的 prev 指向 tail 節點，串起來"""def __init__(self, maxsize=None):self.maxsize = maxsizenode = Node()node.next, node.prev = node, nodeself.root = nodeself.length = 0def __len__(self):return self.lengthdef headnode(self):return self.root.nextdef tailnode(self):return self.root.prevdef append(self, value):    # O(1), 你發現一般不用 for 循環的就是 O(1)，有限個步驟if self.maxsize is not None and len(self) >= self.maxsize:raise Exception('LinkedList is Full')node = Node(value=value)tailnode = self.tailnode() or self.roottailnode.next = nodenode.prev = tailnodenode.next = self.rootself.root.prev = nodeself.length += 1def appendleft(self, value):if self.maxsize is not None and len(self) >= self.maxsize:raise Exception('LinkedList is Full')node = Node(value=value)if self.root.next is self.root:   # emptynode.next = self.rootnode.prev = self.rootself.root.next = nodeself.root.prev = nodeelse:node.prev = self.rootheadnode = self.root.nextnode.next = headnodeheadnode.prev = nodeself.root.next = nodeself.length += 1def remove(self, node):      # O(1)，傳入node 而不是 value 我們就能實現 O(1) 刪除"""remove:param node  # 在 lru_cache 里實際上根據key 保存了整個node:"""if node is self.root:returnelse:    #node.prev.next = node.nextnode.next.prev = node.prevself.length -= 1return nodedef iter_node(self):if self.root.next is self.root:returncurnode = self.root.nextwhile curnode.next is not self.root:yield curnodecurnode = curnode.nextyield curnodedef __iter__(self):for node in self.iter_node():yield node.valuedef iter_node_reverse(self):"""相比單鏈表獨有的反序遍歷"""if self.root.prev is self.root:returncurnode = self.root.prevwhile curnode.prev is not self.root:yield curnodecurnode = curnode.prevyield curnode############################################################
# 分割線，下邊是本章 內容實現
############################################################class Deque(CircularDoubleLinkedList):   # 注意這里我們用到了繼承，嗯，貌似我說過不會用啥 OOP 特性的，抱歉def pop(self):"""刪除尾節點"""if len(self) == 0:raise Exception('empty')tailnode = self.tailnode()value = tailnode.valueself.remove(tailnode)return valuedef popleft(self):if len(self) == 0:raise Exception('empty')headnode = self.headnode()value = headnode.valueself.remove(headnode)return valuedef test_deque():dq = Deque()dq.append(1)dq.append(2)assert list(dq) == [1, 2]dq.appendleft(0)assert list(dq) == [0, 1, 2]dq.pop()assert list(dq) == [0, 1]dq.popleft()assert list(dq) == [1]dq.pop()assert len(dq) == 0class Stack(object):def __init__(self):self.deque = Deque()   # 你可以很容易替換為 python 內置的 collections.dequedef push(self, value):self.deque.append(value)def pop(self):return self.deque.pop()class Stack2(object):def __init__(self):self._deque = deque()def push(self, value):return self._deque.append(value)def pop(self):return self._deque.pop()def empty(self):return len(self._deque) == 0def test_stack():s = Stack()s.push(0)s.push(1)s.push(2)assert s.pop() == 2assert s.pop() == 1assert s.pop() == 0import pytest    # pip install pytestwith pytest.raises(Exception) as excinfo:   # 我們來測試是否真的拋出了異常s.pop()assert 'empty' in str(excinfo.value)if __name__ == '__main__':test_stack()

數據結構頭腦風暴法

當我們不知道使用什么數據結構來解決問題的時候，《程序員面試金典》這本書的第六章提到了一種方式叫做『數據結構頭腦風暴法』。
這種笨方法就是快速過一遍數據結構的列表，然后逐一嘗試各種數據結構看看哪個最適合。

在你實現一個更高級的數據結構的時候，如果腦子沒有思路，不妨嘗試下這個方法，迅速過一遍你所知道的數據結構，看看哪種最適合。(從每個操作的時間復雜度和空間復雜度分析尋找最優解)

思考題

• 上一章我們用數組實現了隊列，其實也能用數組來實現棧，你能自己用數組來實現一個棧的 ADT 嗎？
• 實際上借助 python 內置的 list/collections.deque 結構就很容易實現一個棧，請你嘗試實現，本章我們全部使用自己編寫的數據結構而沒用到 python 內置的數據結構。
• 這里我們自己實現了 Deque，你能用 python 內置的 collections.deque 實現棧嗎？有輪子能直接用的話看起來就簡單多了，這里我們為了學習數據結構的實現就避免了直接使用內置結構
• 哪些經典算法里使用到了棧呢？

Leetcode 練習

https://leetcode.com/problems/implement-queue-using-stacks/