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

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

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

2.棧

2.1 棧的定義

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

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

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

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

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

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

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

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

2.3 用python實(shí)現(xiàn)棧

在前面一章中我們說到，python是一門面向?qū)ο蟮木幊陶Z言，每當(dāng)需要在 Python 中實(shí)現(xiàn)像棧這樣的抽象數(shù)據(jù)類型時(shí)，就可以創(chuàng)建新類。棧的操作通過方法實(shí)現(xiàn)。更進(jìn)一步地說，因?yàn)闂Ｊ窃氐募?，所以完全可以利?Python 提供的強(qiáng)大、簡單的原生集合來實(shí)現(xiàn)。這里我們基于列表來實(shí)現(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)用

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

3. 隊(duì)列

3.1 隊(duì)列的定義

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

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

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

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

它支持以下操作：

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

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

3.3 用python實(shí)現(xiàn)隊(duì)列

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

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

演示：

3.3 隊(duì)列的應(yīng)用

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

4. 雙端隊(duì)列

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

4.1 雙端隊(duì)列的定義

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

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

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

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

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

雙端隊(duì)列支持以下操作：

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

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

4.3 用python實(shí)現(xiàn)雙端隊(duì)列

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

class Deque:
    def __init__(self):#創(chuàng)建新的雙端隊(duì)列
        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):#雙端隊(duì)列的長度
        return len(self.items)

演示：

4.3 雙端隊(duì)列的應(yīng)用

• 回文數(shù)檢測

5.鏈表

5.1 鏈表定義

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

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

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

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

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

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

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

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

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

下面是一些對(duì)鏈表的操作：

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

參考資料：

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

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

最新評(píng)論