python數據結構之棧、隊列及雙端隊列

前文學習：

python數據類型: python數據結構：數據類型.
python的輸入輸出: python數據結構輸入輸出及控制和異常.
python面向對象: python數據結構面向對象.
python算法分析: python數據結構算法分析.

今天來學習數據結構之棧、隊列和雙端隊列，主要是使用python來實現這些基礎的數據結構，瞭解他們的性能，可能還會接觸到二叉樹，還會瞭解用這些結構來解決什麼樣的問題。總而言之，很重要就對瞭。

1.線性數據結構的定義

我們首先學習 4 種簡單而強大的數據結構。棧、隊列、雙端隊列和列表都是有序的數據集合， 其元素的順序取決於添加順序或移除順序。一旦某個元素被添加進來，它與前後元素的相對位置將保持不變。這樣的數據集合經常被稱為線性數據結構。
線性數據結構可以看作有兩端。這兩端有時候被稱作“左端”和“右端”，有時候也被稱作 “前端”和“後端”。當然，它們還可以被稱作“頂端”和“底端”。名字本身並不重要，真正區分線性數據結構的是元素的添加方式和移除方式，尤其是添加操作和移除操作發生的位置。舉例來說，某個數據結構可能隻允許在一端添加新元素，有些則允許從任意一端移除元素。

2.棧

2.1 棧的定義

棧有時也被稱作“下推棧”。它是有序集合，添加操作和移除操作總發生在同一端，即“頂端”，另一端則被稱為“底端”。

棧中的元素離底端越近，代表其在棧中的時間越長，因此棧的底端具有非常重要的意義。最新添加的元素將被最先移除。這種排序原則被稱作 LIFO(last-in first-out)，即後進先出。它提供瞭一種基於在集合中的時間來排序的方式。最近添加的元素靠近頂端，舊元素則靠近底端。

給大傢舉個例子：比如你放書，你最先看過的書會被放在最底下。

棧的特點：每次的操作隻能在棧道頂端進行。先進後出！插入和取出的順序相反。

2.2 棧的數據類型

棧這種數據類型是人為定義的，在基礎數據類型不存在，需要我們自己定義，它有一下操作：

• Stack()創建一個空棧。它不需要參數，且會返回一個空棧
• push(item)將一個元素添加到棧的頂端。它需要一個參數 item，且無返回值
• pop()將棧頂端的元素移除。它不需要參數，但會返回頂端的元素，並且修改棧的內容
• peek()返回棧頂端的元素，但是並不移除該元素。它不需要參數，也不會修改棧的內容
• isEmpty()檢查棧是否為空。它不需要參數，且會返回一個佈爾值
• size()返回棧中元素的數目。它不需要參數，且會返回一個整數。

例如下圖是一個新創建的空棧。展示瞭對棧進行一系列操作的結果。在“棧內容”一列中，棧頂端的元素位於最右側。

2.3 用python實現棧

在前面一章中我們說到，python是一門面向對象的編程語言，每當需要在 Python 中實現像棧這樣的抽象數據類型時，就可以創建新類。棧的操作通過方法實現。更進一步地說，因為棧是元素的集合，所以完全可以利用 Python 提供的強大、簡單的原生集合來實現。這裡我們基於列表來實現棧。

class stack:
    def __init__(self):#構建空棧
        self.items = []
    def isEmpty(self):#判斷是否為空
        return self.item==[]
    def push(self, item):#向棧內押送數據
        self.items.append(item)
    def pop(self):#移除棧頂的元素
        return self.items.pop()
    def peek(self):#返回棧頂頂元素
        return self.items[len(self.items)-1]
    def size(self):#返回棧的長度
        return len(self.items)

演示：

2.4 棧的應用

• 計算機中匹配括號
• 將十進制數轉換成二進制數
• 前序、中序和後序表達式

3. 隊列

3.1 隊列的定義

隊列是有序集合，添加操作發生在“尾部”，移除操作則發生在“頭部”。新元素從尾部進入隊列，然後一直向前移動到頭部，直到成為下一個被移除的元素。
最新添加的元素必須在隊列的尾部等待，在隊列中時間最長的元素則排在最前面。這種排序原則被稱作 FIFO(first-in first-out)，即先進先出，也稱先到先得。

在日常生活中，我們經常排隊，這便是最簡單的隊列例子。進電影院要排隊，在超市結賬要 排隊，買咖啡也要排隊(等著從盤子棧中取盤子)。好的隊列隻允許一頭進，另一頭出，不可能發生插隊或者中途離開的情況，給大傢看一個圖：

3.2 隊列抽象數據類型

隊列抽象數據類型由下面的結構和操作定義。如前所述，隊列是元素的有序集合，添加操作發生在其尾部，移除操作則發生在頭部。隊列的操作順序是 FIFO，

它支持以下操作：

• Queue()創建一個空隊列。它不需要參數，且會返回一個空隊列
• enqueue(item)在隊列的尾部添加一個元素。它需要一個元素作為參數，不返回任何值
• dequeue()從隊列的頭部移除一個元素。它不需要參數，且會返回一個元素，並修改隊列內容
• isEmpty()檢查隊列是否為空。它不需要參數，且會返回一個佈爾值
• size()返回隊列中元素的數目。它不需要參數，且會返回一個整數

如下圖：展示瞭對 q 進行一系列操作的結果。假設 q 是一個新創建的空隊列。在“隊列內容”列中，隊列的頭部位於右端。4 是第一個被添加到隊列中的元素，因此它也是第一個被移除的元素。

3.3 用python實現隊列

創建一個新類來實現隊列抽象數據類型是十分合理的。像之前一樣，我們利用簡潔強大的列表來實現隊列。假設隊列的尾部在列表的位置 0 處。如此一來，便可以使用 insert 函數向隊列的尾部添加新元素。pop 則可 用於移除隊列頭部的元素(列表中的最後一個元素)。這意味著添加操作的時間復雜度是 O(n) ， 移除操作則是O(1)。

class queue:
    def __init__(self): #構建初始隊列
        self.items=[]
    def isEmpty(self):#判斷是否為空
        return self.items==[]
    def enqueue(self,item):#加入隊列
        self.items.insert(0,item)
    def dequeue(self):#刪除隊列元素
        return self.items.pop()
    def size(self):#展示隊列長度
        return len(self.items)

演示：

3.3 隊列的應用

• 著名的約瑟夫環
• 排隊任務

4. 雙端隊列

雙端隊列與棧和隊列不同的是，雙端隊列的限制很少。註意，不要把它的英文名 deque(與 deck 同音)和隊列的移除操作 dequeue 搞混瞭。

4.1 雙端隊列的定義

雙端隊列是與隊列類似的有序集合。它有一前、一後兩端，元素在其中保持自己的位置。與 隊列不同的是，雙端隊列對在哪一端添加和移除元素沒有任何限制。新元素既可以被添加到前端， 也可以被添加到後端。同理，已有的元素也能從任意一端移除。某種意義上，雙端隊列是棧和隊 列的結合。

下圖展示瞭由 Python 數據對象組成的雙端隊列：

值得註意的是，盡管雙端隊列有棧和隊列的很多特性，但是它並不要求按照這兩種數據結構分別規定的 LIFO 原則和 FIFO 原則操作元素。具體的排序原則取決於其使用者。

4.2 雙端隊列抽象數據類型

雙端隊列抽象數據類型由下面的結構和操作定義。如前所述，雙端隊列是元素的有序集合，其任何一端都允許添加或移除元素。

雙端隊列支持以下操作：

• Deque()創建一個空的雙端隊列。它不需要參數，且會返回一個空的雙端隊列。
• addFront(item)將一個元素添加到雙端隊列的前端。它接受一個元素作為參數，沒有返回值。
• addRear(item)將一個元素添加到雙端隊列的後端。它接受一個元素作為參數，沒有返 回值。
• removeFront()從雙端隊列的前端移除一個元素。它不需要參數，且會返回一個元素， 並修改雙端隊列的內容。
• removeRear()從雙端隊列的後端移除一個元素。它不需要參數，且會返回一個元素， 並修改雙端隊列的內容。
• isEmpty()檢查雙端隊列是否為空。它不需要參數，且會返回一個佈爾值。
• size()返回雙端隊列中元素的數目。它不需要參數，且會返回一個整數。

下圖展示瞭對 d 進行一系列操作的結果。假設 d 是一個新創建的空雙端隊列，註意，前端 在列表的右端。記住前端和後端的位置可以防止混淆。

4.3 用python實現雙端隊列

和前面一樣，我們通過創建一個新類來實現雙端隊列抽象數據類型。Python 列表再一次提供瞭很多簡便的方法來幫助我們構建雙端隊列。在下圖中，我們假設雙端隊列的後端是列表的位置 0 處。

class Deque:
    def __init__(self):#創建新的雙端隊列
        self.items = []
    def isEmpty(self):#判斷是否為空
        return self.items == []
    def addFront(self, item):#在前端添加元素
        self.items.append(item)
    def addRear(self, item):#在後端添加字符
        self.items.insert(0, item)
    def removeFront(self):#移除前端的字符
        return self.items.pop()
    def removeRear(self):#在後端異常字符
        return self.items.pop(0)
    def size(self):#雙端隊列的長度
        return len(self.items)

演示：

4.3 雙端隊列的應用

• 回文數檢測

5.鏈表

5.1 鏈表定義

鏈表必須指明列表中第一個元素的位置。一旦知道第一個元素的位置，就能根據 其中的鏈接信息訪問第二個元素，接著訪問第三個元素，依此類推。指向鏈表第一個元素的引用被稱作頭。最後一個元素需要知道自己沒有下一個元素。

5.2 用python實現鏈表

==節點(node)==是構建鏈表的基本數據結構。每一個節點對象都必須持有至少兩份信息。首先,節點必須包含列表元素，我們稱之為節點的數據變量。其次,節點必須保存指向下一個節點的引用。

#聲明一個鏈表節點的結構
class Node:
    def __init__(self, initdata):#初始化節點，next為none
        self.data = initdata
        self.next = None
    def getData(self):#節點的值
        return self.data
    def getNext(self):#節點的下一個節點
        return self.next
    def setData(self, newdata):#設置節點的值
        self.data = newdata
    def setNext(self, newnext):#設置節點的下一節點連接值
        self.next = newnext

鏈表是基於節點集合來構建的，每一個節點都通過顯式的引用指向下一個節點。隻要知道第一個節點的位置(第一個節點包含第一個元素)，其後的每一個元素都能通過下一個引用找到。因此，節點類必須包含指向第一個節點的引用。註意，每一個列表對象都保存瞭指向列表頭部的引用。

#聲明一個鏈表開頭
class UnorderedList:
    def __init__(self):
        self.head = None

最開始構建列表時，其中沒有元素,賦值語句 mylist = UnorderedList()將創建下圖的鏈表，與在 Node 類中一樣，特殊引用值 None 用於表明列表的頭部沒有指向任何節點。列表的頭部指向包含列表第 一個元素的節點。這個節點包含指向下一個節點(元素)的引用，依此類推。非常重要的一點是， 列表類本身並不包含任何節點對象，而隻有指向整個鏈表結構中第一個節點的引用。

關於鏈表的操作我們這裡就一下子給大傢瞭：

#聲明節點結構，在創建鏈表是會用到改結構
class Node:
    def __init__(self, initdata):#初始化節點，next為none
        self.data = initdata
        self.next = None
    def getData(self):#節點的值
        return self.data
    def getNext(self):#節點的下一個節點
        return self.next
    def setData(self, newdata):#設置節點的值
        self.data = newdata
    def setNext(self, newnext):#設置節點的下一節點連接值
        self.next = newnext
#聲明一個鏈表結構，裡面包含很多節點
class UnorderedList:
    def __init__(self):
        self.head = None 
    def add(self, item): #增加一個節點
        temp = Node(item) 
        temp.setNext(self.head) 
        self.head = temp
        
    def length(self): #鏈表長度
        current = self.head 
        count = 0     
        while current != None: 
            count = count + 1 
            current = current.getNext() 
        return count

    def search(self, item): #查找是否存在該節點
        current = self.head 
        found = False 
        while current != None and not found: 
            if current.getData() == item: 
                found = True
            else: 
                current = current.getNext() 
        return found
    def remove(self, item): #移除該節點
        current = self.head 
        previous = None 
        found = False 
        while not found: 
            if current.getData() == item: 
                found = True 
            else: 
                previous = current 
                current = current.getNext() 
        if previous == None: 
            self.head = current.getNext() 
        else: 
            previous.setNext(current.getNext())

下面是一些對鏈表的操作：

總結：
其實這裡隻是簡單介紹瞭一下棧、隊列和鏈表，以及簡單的實現，其實他們實現的方式有很多種，我們這裡隻用瞭簡單的實現方式。

參考資料：

• 《python數據結構與算法》
• 《大話數據結構》

到此這篇關於python數據結構之棧、隊列及雙端隊列的文章就介紹到這瞭,更多相關python棧、隊列和雙端隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：

• python實現雙鏈表
• Python線性表種的單鏈表詳解
• python單向循環鏈表實例詳解
• 帶你瞭解Java數據結構和算法之鏈表
• python雙向循環鏈表實例詳解