笨辦法學 Python · 續 練習 15：棧和隊列

練習 15：棧和隊列

原文： Exercise 15: Stacks and Queues 譯者： 飛龍 協定： CC BY-NC-SA 4.0 自豪地采用 谷歌翻譯

當處理資料結構時，你将經常遇到類似于另一種結構的結構。

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

相同，而事實上我隻是複制過來并更名：

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

的概念。

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

資料結構？這如何改變你的設計？