前文學(xué)習(xí)：

python數(shù)據(jù)類型: python數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)類型.
python的輸入輸出: python數(shù)據(jù)結(jié)構(gòu)輸入輸出及控制和異常.
python面向?qū)ο? python數(shù)據(jù)結(jié)構(gòu)面向?qū)ο?
python算法分析: python數(shù)據(jù)結(jié)構(gòu)算法分析.

今天來學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之棧、隊列和雙端隊列，主要是使用python來實現(xiàn)這些基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，了解他們的性能，可能還會接觸到二叉樹，還會了解用這些結(jié)構(gòu)來解決什么樣的問題。總而言之，很重要就對了。

1.線性數(shù)據(jù)結(jié)構(gòu)的定義

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

2.棧

2.1 棧的定義

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

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

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

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

2.2 棧的數(shù)據(jù)類型

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

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

例如下圖是一個新創(chuàng)建的空棧。展示了對棧進行一系列操作的結(jié)果。在“棧內(nèi)容”一列中，棧頂端的元素位于最右側(cè)。

2.3 用python實現(xiàn)棧

在前面一章中我們說到，python是一門面向?qū)ο蟮木幊陶Z言，每當需要在 Python 中實現(xiàn)像棧這樣的抽象數(shù)據(jù)類型時，就可以創(chuàng)建新類。棧的操作通過方法實現(xiàn)。更進一步地說，因為棧是元素的集合，所以完全可以利用 Python 提供的強大、簡單的原生集合來實現(xiàn)。這里我們基于列表來實現(xiàn)棧。

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

演示：

2.4 棧的應(yīng)用

• 計算機中匹配括號
• 將十進制數(shù)轉(zhuǎn)換成二進制數(shù)
• 前序、中序和后序表達式

3. 隊列

3.1 隊列的定義

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

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

3.2 隊列抽象數(shù)據(jù)類型

隊列抽象數(shù)據(jù)類型由下面的結(jié)構(gòu)和操作定義。如前所述，隊列是元素的有序集合，添加操作發(fā)生在其尾部，移除操作則發(fā)生在頭部。隊列的操作順序是 FIFO，

它支持以下操作：

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

如下圖：展示了對 q 進行一系列操作的結(jié)果。假設(shè) q 是一個新創(chuàng)建的空隊列。在“隊列內(nèi)容”列中，隊列的頭部位于右端。4 是第一個被添加到隊列中的元素，因此它也是第一個被移除的元素。

3.3 用python實現(xiàn)隊列

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

class queue:
    def __init__(self): #構(gòu)建初始隊列
        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 隊列的應(yīng)用

• 著名的約瑟夫環(huán)
• 排隊任務(wù)

4. 雙端隊列

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

4.1 雙端隊列的定義

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

下圖展示了由 Python 數(shù)據(jù)對象組成的雙端隊列：

值得注意的是，盡管雙端隊列有棧和隊列的很多特性，但是它并不要求按照這兩種數(shù)據(jù)結(jié)構(gòu)分別規(guī)定的 LIFO 原則和 FIFO 原則操作元素。具體的排序原則取決于其使用者。

4.2 雙端隊列抽象數(shù)據(jù)類型

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

雙端隊列支持以下操作：

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

下圖展示了對 d 進行一系列操作的結(jié)果。假設(shè) d 是一個新創(chuàng)建的空雙端隊列，注意，前端 在列表的右端。記住前端和后端的位置可以防止混淆。

4.3 用python實現(xiàn)雙端隊列

和前面一樣，我們通過創(chuàng)建一個新類來實現(xiàn)雙端隊列抽象數(shù)據(jù)類型。Python 列表再一次提供了很多簡便的方法來幫助我們構(gòu)建雙端隊列。在下圖中，我們假設(shè)雙端隊列的后端是列表的位置 0 處。

class Deque:
    def __init__(self):#創(chuàng)建新的雙端隊列
        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 雙端隊列的應(yīng)用

• 回文數(shù)檢測

5.鏈表

5.1 鏈表定義

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

5.2 用python實現(xiàn)鏈表

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

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

鏈表是基于節(jié)點集合來構(gòu)建的，每一個節(jié)點都通過顯式的引用指向下一個節(jié)點。只要知道第一個節(jié)點的位置(第一個節(jié)點包含第一個元素)，其后的每一個元素都能通過下一個引用找到。因此，節(jié)點類必須包含指向第一個節(jié)點的引用。注意，每一個列表對象都保存了指向列表頭部的引用。

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

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

關(guān)于鏈表的操作我們這里就一下子給大家了：

#聲明節(jié)點結(jié)構(gòu)，在創(chuàng)建鏈表是會用到改結(jié)構(gòu)
class Node:
    def __init__(self, initdata):#初始化節(jié)點，next為none
        self.data = initdata
        self.next = None
    def getData(self):#節(jié)點的值
        return self.data
    def getNext(self):#節(jié)點的下一個節(jié)點
        return self.next
    def setData(self, newdata):#設(shè)置節(jié)點的值
        self.data = newdata
    def setNext(self, newnext):#設(shè)置節(jié)點的下一節(jié)點連接值
        self.next = newnext
#聲明一個鏈表結(jié)構(gòu)，里面包含很多節(jié)點
class UnorderedList:
    def __init__(self):
        self.head = None 
    def add(self, item): #增加一個節(jié)點
        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): #查找是否存在該節(jié)點
        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): #移除該節(jié)點
        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())

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

總結(jié)：
其實這里只是簡單介紹了一下棧、隊列和鏈表，以及簡單的實現(xiàn)，其實他們實現(xiàn)的方式有很多種，我們這里只用了簡單的實現(xiàn)方式。

參考資料：

• 《python數(shù)據(jù)結(jié)構(gòu)與算法》
• 《大話數(shù)據(jù)結(jié)構(gòu)》

到此這篇關(guān)于python數(shù)據(jù)結(jié)構(gòu)之棧、隊列及雙端隊列的文章就介紹到這了,更多相關(guān)python棧、隊列和雙端隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論