# 練習 15：棧和隊列 > 原文：[Exercise 15: Stacks and Queues](https://learncodethehardway.org/more-python-book/ex15.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 當處理數據結構時，你將經常遇到類似于另一種結構的結構。`Stack`類似于練習13中的`SingleLinkedList`，以及`Queue`類似于練習14中的`DoubleLinkedList`，唯一區別是`Stack`和`Queue`限制了可能的操作，以簡化它們的使用方式。這有助于減少缺陷，因為你不能意外地像`Queue`那樣使用`Stack`并導致問題。在`Stack`中，節點被“壓入”“棧頂”，然后從頂部“彈出”。在隊列中，節點壓入“尾部”，之后從“頭部”彈出。這些操作都是`SingleLinkedList`和`DoubleLinkedList`的簡化，其中`Stack`只允許`push`和`pop`操作，`Queue`只允許`shift`和`unshift`。 > 譯者注：實際上是`push`和`unshift`。 當可視化堆棧時，你應該想到你的地板上的一堆書。想像我在書架上的那種很重的藝術書，如果我堆疊了20個，可能會重約100磅。當你為這些書構建棧的時候，你不能抬起整個棧，并且把書放在底部，對吧？不，你把書放在棧的頂部。你把它放在那兒，但我們也可以使用“推”描述這個動作。如果你想從棧中獲取一本書，你可能會抬起一些書，然后抓住一本書，但是最終你可能要從頂部拿出一些書，才能獲取底部得數。你可以從頂部抬起每本書，或者在我們的例子中，我們會說“從頂部彈出一本書”。 如果你想像在銀行排隊，隊列有“頭部”和“尾部”，可視化隊列是最簡單的。通常有一個繩索迷宮，它的末尾有一個入口，出口處是檢票員。你可以通過進入這條繩索迷宮的“尾部”進入隊列，我們??稱之為`shift`，因為這是`Queue`數據結構中的常見編程屬于。一旦你進入銀行（隊列），你不能越過等候線然后離開，否則其余的人會生氣。所以你必須等待，隨著你前面的每個人都離開了等候線（對你而言是`unshift `），你離“頭部”更近了。一旦你達到了頭部，那么你可以退出，我們稱之為`unshift `。 很多時候，你可以找到數據結構的真實世界示例，來幫助你可視化其工作原理。你現在應該花點時間來繪制這些場景，或者實際上得到書籍的棧并測試這些操作。你可以找到與`Stack`和`Queue`類似的其他真實情況嗎？ ## 挑戰練習 我現在打算讓你做一個基于代碼的挑戰練習，并且從它們的描述中實現數據結構。在這個挑戰中，你首先需要使用這里的起始代碼，以及你從練習 13 中了解的`SingleLinkedList`，實現`Stack`數據結構。完成之后，你將嘗試從零開始實現`Queue`數據結構。 `StackNode`節點類幾乎和`SingleLinkedListNode`相同，而事實上我只是復制過來并更名： ```py class StackNode(object): def __init__(self, value, nxt): self.value = value self.next = nxt def __repr__(self): nval = self.next and self.next.value or None return f"[{self.value}:{repr(nval)}]" ``` `Stack `控制類和`SingleLinkedList `十分類似，除了我使用`top `代替了`first`。這樣匹配`Stack`的概念。 ```py class Stack(object): def __init__(self): self.top = None def push(self, obj): """Pushes a new value to the top of the stack.""" def pop(self): """Pops the value that is currently on the top of the stack.""" def top(self): """Returns a *reference* to the first item, does not remove.""" def count(self): """Counts the number of elements in the stack.""" def dump(self, mark="----"): """Debugging function that dumps the contents of the stack.""" ``` 現在你的挑戰是實現`Stack`，并為其執行測試，類似于在練習 13 中進行的測試。請確保你的測試涵蓋了每一個操作，你可以以任何方式。記住，盡管如此，堆棧的`push`操作必須在頂部，所以有到頂部的鏈接。 一旦你使`Stack`正常工作，你應該實現`Queue`，但它基于`DoubleLinkedList`。（譯者注：其實單鏈表也行，因為只有尾部彈出的操作比較困難。你可以在尾部插入，在頭部彈出。）`Stack`中的內容應該與`SingleLinkedList`基本內部結構相同，只需更改允許的功能。`Queue`也一樣。花點時間來繪制隊列的工作原理，然后弄清楚它如何限制`DoubleLinkedList`。一旦你完成了，創建你的隊列。 ## 破壞它 破壞這些數據結構僅僅是不要維持約束。看看如果一個操作無法使用正確的尾部會發生什么。 你可能還注意到，它有“偏移一位”的持久性錯誤。在我的設計中，當結構為空時，我設置了`self.top = None`。這意味著當你達到 0 個元素時，你必須對`self.top`做一些特殊處理。一個替代方法是使`self.top`總是指向一個`StackNode`（偽造的頭節點），并假設當你有這個最后的元素時，結構是空的。嘗試它，看看它如何改變你的實現。這樣會更容易出錯還是更不容易出錯？ ## 深入學習 這些數據結構有很多操作是非常低效的。回顧你為每個數據結構編寫的代碼，并嘗試猜測哪些函數最慢。一旦你有了想法，嘗試解釋為什么他們可能很慢。研究其他人對這些數據結構的看法。在練習 18 和 19 中，你將學習對這些數據結構進行一些性能分析并進行調整。 最后，你真的需要實現一個全新的數據結構嗎，還是簡單地“包裝” `SingleLinkedList`和`DoubleLinkedList`數據結構？這如何改變你的設計？