Python常用隊(duì)列全面詳細(xì)梳理

更新時(shí)間：2023年01月20日 10:07:04 作者：楊jun堅(jiān)

隊(duì)列是限制在兩端進(jìn)行插入和操作的線性表，允許存入操作的一段叫“隊(duì)尾”，刪除操作的一端叫“隊(duì)頭”，隊(duì)列的特點(diǎn)：隊(duì)列只能在隊(duì)頭和隊(duì)尾進(jìn)行數(shù)據(jù)操作，隊(duì)列模型具有先進(jìn)先出的規(guī)律

一，隊(duì)列

和棧一樣，隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。隊(duì)列是一種操作受限制的線性表，進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒(méi)有元素時(shí)，稱為空隊(duì)列。

二，常見(jiàn)隊(duì)列

1，F(xiàn)IFO隊(duì)列

基本FIFO隊(duì)列先進(jìn)先出 FIFO即First in First Out,先進(jìn)先出。

調(diào)用queue.Queue

from queue import Queue
fifo_queue = Queue()
fifo_queue.put(1)  # 隊(duì)尾插入新元素
fifo_queue.put(2)
fifo_queue.put(3)
print(fifo_queue.queue)
print(fifo_queue.get())  # 隊(duì)頭取出元素
print(fifo_queue.queue)

鏈表實(shí)現(xiàn)

class LNode(object):
    def __init__(self, item, next_=None):
        self.item = item
        self.next = next_
class FIFOQueue(object):
    def __init__(self):
        """初始化"""
        self.head = None
        self.rear = None
    def is_empty(self):
        """判斷是否為空"""
        return self.head is None
    def size(self):
        """獲取隊(duì)列長(zhǎng)度"""
        cur = self.head
        count = 0
        while True:
            count += 1
            if cur == self.rear:
                break
            cur = cur.next
        return count
    def travel(self):
        """遍歷隊(duì)列"""
        if self.is_empty():
            print('queue is empty')
            return
        else:
            cur = self.head
            while True:
                print(cur.item, end='')
                if cur.next:
                    print(',', end='')
                if cur == self.rear:
                    break
                cur = cur.next
            print('')
    def push(self, val):
        """隊(duì)尾插入新元素"""
        p = LNode(val)
        if self.is_empty():
            self.head = p
            self.rear = p
        else:
            self.rear.next = p
            self.rear = self.rear.next
    def get(self):
        """獲取隊(duì)頭元素"""
        if self.is_empty():
            print('queue is empty')
            return
        else:
            e = self.head.item
            self.head = self.head.next
            return e
if __name__ == '__main__':
    FIFOQueue = FIFOQueue()
    FIFOQueue.push(1)
    FIFOQueue.push(2)
    FIFOQueue.push(3)
    FIFOQueue.push(4)
    FIFOQueue.travel()  # 1,2,3,4
    print(FIFOQueue.get())  # 1
    print(FIFOQueue.get())  # 2
    FIFOQueue.travel()  # 3,4

list實(shí)現(xiàn)

# list 實(shí)現(xiàn)
class FIFOQueue(object):
    def __init__(self):
        self.queue = list()
    def size(self):
        return len(self.queue)
    def travel(self):
        print(self.queue)
    def push(self, val):
        self.queue.append(val)
    def get(self):
        return self.queue.pop(0)
if __name__ == '__main__':
    FIFOQueue = FIFOQueue()
    FIFOQueue.push(1)
    FIFOQueue.push(2)
    FIFOQueue.push(3)
    FIFOQueue.push(4)
    FIFOQueue.travel()  # 1,2,3,4
    print(FIFOQueue.get())  # 1
    print(FIFOQueue.get())  # 2
    FIFOQueue.travel()  # 3,4

2，LIFO隊(duì)列

LIFO即Last in First Out,后進(jìn)先出。與棧的類似，在隊(duì)尾進(jìn)行插入和刪除操作。

調(diào)用queue.LifoQueue

from queue import LifoQueue
lifo_queue = LifoQueue()
lifo_queue.put(1)  # 隊(duì)尾插入新元素
lifo_queue.put(2)
lifo_queue.put(3)
print(lifo_queue.queue)
print(lifo_queue.get())  # 隊(duì)尾取出元素
print(lifo_queue.queue)

鏈表實(shí)現(xiàn)

將鏈表頭部作為隊(duì)列尾部，在鏈表頭部進(jìn)行插入和刪除操作。

class LNode(object):
    def __init__(self, item, next_=None):
        self.item = item
        self.next = next_
class LIFOQueue(object):
    def __init__(self):
        """初始化"""
        self.head = None
    def is_empty(self):
        """判斷是否為空"""
        return self.head is None
    def size(self):
        """獲取隊(duì)列長(zhǎng)度"""
        cur = self.head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count
    def travel(self):
        """遍歷隊(duì)列"""
        travel_list = []
        cur = self.head
        while cur:
            travel_list.append(cur.item)
            cur = cur.next
        travel_list.reverse()
        print(travel_list)
    def push(self, val):
        """頭部插入"""
        self.head = LNode(val, self.head)
    def get(self):
        """獲取隊(duì)頭元素"""
        if self.is_empty():
            print('queue is empty')
            return
        else:
            e = self.head.item
            self.head = self.head.next
            return e
if __name__ == '__main__':
    LIFOQueue = LIFOQueue()
    LIFOQueue.push(1)
    LIFOQueue.push(2)
    LIFOQueue.push(3)
    LIFOQueue.push(4)
    LIFOQueue.travel()  # 1,2,3,4
    print(LIFOQueue.get())  # 4
    print(LIFOQueue.get())  # 3
    LIFOQueue.travel()  # 1,2

List實(shí)現(xiàn)

# list 實(shí)現(xiàn)
class LIFOQueue(object):
    def __init__(self):
        self.queue = list()
    def size(self):
        return len(self.queue)
    def travel(self):
        print(self.queue)
    def push(self, val):
        self.queue.append(val)
    def get(self):
        return self.queue.pop()
if __name__ == '__main__':
    LIFOQueue = LIFOQueue()
    LIFOQueue.push(1)
    LIFOQueue.push(2)
    LIFOQueue.push(3)
    LIFOQueue.push(4)
    LIFOQueue.travel()  # 1,2,3,4
    print(LIFOQueue.get())  # 4
    print(LIFOQueue.get())  # 3
    LIFOQueue.travel()  # 1,2

3，雙向隊(duì)列

雙端隊(duì)列（deque，全名 double-ended queue），是一種具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。雙端隊(duì)列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進(jìn)行。雙端隊(duì)列可以在隊(duì)列任意一端入隊(duì)和出隊(duì)。

調(diào)用collections .deque

collections 是 python 內(nèi)建的一個(gè)集合模塊，里面封裝了許多集合類，其中隊(duì)列相關(guān)的集合只有一個(gè)：deque。

deque 是雙邊隊(duì)列（double-ended queue），具有隊(duì)列和棧的性質(zhì)，在 list 的基礎(chǔ)上增加了移動(dòng)、旋轉(zhuǎn)和增刪等。

deque(maxlen=3)，通過(guò)maxlen參數(shù)，可以創(chuàng)建固定長(zhǎng)度的隊(duì)列，當(dāng)新元素加入隊(duì)列且隊(duì)列已滿，會(huì)自動(dòng)從另一端移除首個(gè)元素。不指定maxlen，得到無(wú)界限的隊(duì)列。

from collections import deque
d = deque([])
d.append('a')  # 在最右邊添加一個(gè)元素，此時(shí) d=deque('a')
print(d)
d.appendleft('b')  # 在最左邊添加一個(gè)元素，此時(shí) d=deque(['b', 'a'])
print(d)
d.extend(['c', 'd'])  # 在最右邊添加所有元素，此時(shí) d=deque(['b', 'a', 'c', 'd'])
print(d)
d.extendleft(['e', 'f'])  # 在最左邊添加所有元素，此時(shí) d=deque(['f', 'e', 'b', 'a', 'c', 'd'])
print(d)
d.pop()  # 將最右邊的元素取出，返回 'd'，此時(shí) d=deque(['f', 'e', 'b', 'a', 'c'])
print(d)
d.popleft()  # 將最左邊的元素取出，返回 'f'，此時(shí) d=deque(['e', 'b', 'a', 'c'])
print(d)
d.rotate(-2)  # 向左旋轉(zhuǎn)兩個(gè)位置（正數(shù)則向右旋轉(zhuǎn)），此時(shí) d=deque(['a', 'c', 'e', 'b'])
print(d)

雙向鏈表實(shí)現(xiàn)

class DLNode(object):
    def __init__(self, item, prior_=None, next_=None):
        self.item = item
        self.prior = prior_
        self.next = next_
class DQueue(object):
    def __init__(self):
        self.head = None    # 頭指針
        self.rear = None    # 尾制造
    def is_empty(self):
        return self.head is None
    def length(self):
        if self.is_empty():
            print('queue is empty')
            return
        else:
            cur = self.head
            count = 0
            while True:
                count += 1
                if cur == self.rear:
                    break
                cur = cur.next
            return count
    def travel(self):
        """遍歷隊(duì)列"""
        if self.is_empty():
            print('queue is empty')
            return
        else:
            cur = self.head
            while True:
                print(cur.item, end='')
                if cur.next:
                    print(',', end='')
                if cur == self.rear:
                    break
                cur = cur.next
            print('')
    def push_rear(self, val):
        """隊(duì)尾插入元素"""
        p = DLNode(val)
        if self.is_empty():
            self.head = p
            self.rear = p
        else:
            self.rear.next = p
            p.prior = self.rear
            self.rear = self.rear.next
    def push_head(self, val):
        """隊(duì)頭插入元素"""
        p = DLNode(val)
        if self.is_empty():
            self.head = p
            self.rear = p
        else:
            p.next = self.head
            self.head.prior = p
            self.head = p
    def pop_rear(self):
        """獲取隊(duì)尾元素"""
        if self.is_empty():
            print('queue is empty')
            return
        else:
            p = self.rear
            self.rear = self.rear.prior
            self.rear.next = None
            return p.item
    def pop_head(self):
        """獲取隊(duì)頭元素"""
        if self.is_empty():
            print('queue is empty')
            return
        else:
            e = self.head.item
            self.head = self.head.next
            return e
if __name__ == '__main__':
    DQueue = DQueue()
    DQueue.push_head(1)
    DQueue.push_head(2)
    DQueue.push_head(3)
    DQueue.travel()  # 3,2,1
    DQueue.push_rear('a')
    DQueue.push_rear('b')
    DQueue.travel()  # 3,2,1,a,b
    print(DQueue.pop_head())  # 3
    print(DQueue.pop_rear())  # b
    print(DQueue.pop_rear())  # a
    DQueue.travel()  # 2,1

list實(shí)現(xiàn)

class DQueue:
    """雙端隊(duì)列"""
    def __init__(self):
        self.queue = []
    def push_head(self, val):
        """從隊(duì)頭加入一個(gè)元素"""
        self.queue.insert(0, val)
    def push_rear(self, val):
        """從隊(duì)尾加入一個(gè)元素"""
        self.queue.append(val)
    def pop_head(self):
        """從隊(duì)頭刪除一個(gè)元素"""
        return self.queue.pop(0)
    def pop_rear(self):
        """從隊(duì)尾刪除一個(gè)元素"""
        return self.queue.pop()
    def is_empty(self):
        """是否為空"""
        return self.queue == []
    def size(self):
        """隊(duì)列長(zhǎng)度"""
        return len(self.queue)
    def travel(self):
        print(self.queue)
if __name__ == "__main__":
    DQueue = DQueue()
    DQueue.push_head(1)
    DQueue.push_head(2)
    DQueue.push_head(3)
    DQueue.travel()  # [3, 2, 1]
    DQueue.push_rear('a')
    DQueue.push_rear('b')
    DQueue.travel()  # [3, 2, 1, 'a', 'b']
    print(DQueue.pop_head())  # 3
    print(DQueue.pop_rear())  # b
    print(DQueue.pop_rear())  # a
    DQueue.travel()  # [2, 1]

4，優(yōu)先級(jí)隊(duì)列

優(yōu)先級(jí)隊(duì)列是一種容器型數(shù)據(jù)結(jié)構(gòu)，它能管理一隊(duì)記錄，并按照排序字段（例如一個(gè)數(shù)字類型的權(quán)重值）為其排序。由于是排序的，所以在優(yōu)先級(jí)隊(duì)列中你可以快速獲取到最大的和最小的值。

可以認(rèn)為優(yōu)先級(jí)隊(duì)列是一種修改過(guò)的普通隊(duì)列：普通隊(duì)列依據(jù)記錄插入的時(shí)間來(lái)獲取下一個(gè)記錄，而優(yōu)先級(jí)隊(duì)列依據(jù)優(yōu)先級(jí)來(lái)獲取下一個(gè)記錄，優(yōu)先級(jí)取決于排序字段的值。

優(yōu)先級(jí)隊(duì)列常用來(lái)解決調(diào)度問(wèn)題，比如給緊急的任務(wù)更高的優(yōu)先級(jí)。以操作系統(tǒng)的任務(wù)調(diào)度為例：高優(yōu)先級(jí)的任務(wù)（比如實(shí)時(shí)游戲）應(yīng)該先于低優(yōu)先級(jí)的任務(wù)（比如后臺(tái)下載軟件更新）執(zhí)行。

調(diào)用queue.PriorityQueue

在 Python 中，內(nèi)置的標(biāo)準(zhǔn)庫(kù)提供了兩種實(shí)現(xiàn)優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，分別是 heapq 模塊和 PriorityQueue 模塊，

最小優(yōu)先級(jí)隊(duì)列

更小的值具有更高的優(yōu)先級(jí)，也就是會(huì)被最先輸出

# 優(yōu)先級(jí)隊(duì)列
from queue import PriorityQueue as PQ
Pqueue = PQ()
Pqueue.put((1, 'a'))
Pqueue.put((3, 'c'))
Pqueue.put((2, 'b'))
Pqueue.put((2, 'd'))
Pqueue.put((5, 'e'))
print(Pqueue.queue)  # [(1, 'a'), (2, 'd'), (2, 'b'), (3, 'c'), (5, 'e')]
while not Pqueue.empty():
    print(Pqueue.get())
# (1, 'a')
# (2, 'b')
# (2, 'd')
# (3, 'c')
# (5, 'e')

最大優(yōu)先級(jí)隊(duì)列

更大的值具有更高的優(yōu)先級(jí)，也就是會(huì)被最先輸出。

from queue import PriorityQueue as PQ
Pqueue = PQ()
Pqueue.put((-1, 'a'))
Pqueue.put((-3, 'c'))
Pqueue.put((-2, 'b'))
Pqueue.put((-2, 'd'))
Pqueue.put((-5, 'e'))
print(Pqueue.queue)  # [(-5, 'e'), (-3, 'c'), (-2, 'b'), (-1, 'a'), (-2, 'd')]
while not Pqueue.empty():
    print(Pqueue.get())
# (-5, 'e')
# (-3, 'c')
# (-2, 'b')
# (-2, 'd') 當(dāng)兩個(gè)對(duì)象的優(yōu)先級(jí)一致時(shí)，按照插入順序排列
# (-1, 'a')

基于 heapq 實(shí)現(xiàn)

heapq 涉及到另一種數(shù)據(jù)結(jié)構(gòu)“堆”，用heapq 實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，也是基于最小堆，最大堆實(shí)現(xiàn)，這些在后面“堆”再一起研究下。

import heapq
class PriorityQueue(object):
    def __init__(self):
        self._queue = []
        # self._index = 0
    def push(self, item, priority):
        """
        隊(duì)列由 (priority, index, item) 形式組成
        priority 默認(rèn)是最小優(yōu)先級(jí)，增加 "-" 實(shí)現(xiàn)最大優(yōu)先級(jí)，
        index 是為了當(dāng)兩個(gè)對(duì)象的優(yōu)先級(jí)一致時(shí)，按照插入順序排列
        """
        heapq.heappush(self._queue, (-priority, item))
        # self._index += 1
    def pop(self):
        """
        彈出優(yōu)先級(jí)最高的對(duì)象
        """
        return heapq.heappop(self._queue)[-1]
    def qsize(self):
        return len(self._queue)
    def empty(self):
        return True if not self._queue else False
if __name__ == '__main__':
    PQueue = PriorityQueue()
    PQueue.push('a', 1)
    PQueue.push('c', 3)
    PQueue.push('b', 2)
    PQueue.push('d', 2)
    PQueue.push('e', 5)
    PQueue.push('f', 1)
    while not PQueue.empty():
        print(PQueue.pop())    # e c b d a f

5，循環(huán)隊(duì)列

在之前實(shí)現(xiàn)的隊(duì)列時(shí)，都為固定隊(duì)列長(zhǎng)度，都創(chuàng)建無(wú)限隊(duì)列，當(dāng)隊(duì)列空間有限時(shí)，插入和刪除元素會(huì)有問(wèn)題呢？

假定用長(zhǎng)度為6的數(shù)組，表示長(zhǎng)度為6的隊(duì)列。隊(duì)列中已經(jīng)有三個(gè)元素a1、a2、a3。

如果新插入元素，只需要在隊(duì)尾插入便可，在下標(biāo)3的位置插入新元素a4，入隊(duì)列的時(shí)間復(fù)雜度O(1)。

如果刪除元素，當(dāng)a1出隊(duì)列后，其后面的a2、a3、a4則需要向前移動(dòng)一個(gè)位置，就好日常排隊(duì)時(shí)，當(dāng)前面人離開(kāi)，后面的隊(duì)伍都往前移動(dòng)一步，所以出隊(duì)列的時(shí)間復(fù)雜度為O(n)。

這種效率顯然是不可以接受的，那么能不能不讓所有成員都往前挪一位呢？

所以在原來(lái)的基礎(chǔ)上，加入兩個(gè)變量front、rear分別存儲(chǔ)隊(duì)頭和隊(duì)尾的下標(biāo)。

此時(shí)front =0 ,rear = 3。

當(dāng)有新元素插入隊(duì)尾時(shí)，rear = rear+1。

當(dāng)有元素出隊(duì)列時(shí)，front = front + 1

這樣一來(lái)，似乎不將后面所有成員往前挪，只需維護(hù)一下front的指向（front += 1）就可以保證隊(duì)首，但是，當(dāng)遇到下面這情況時(shí)，就存在“假溢出”的情況。

將a2、a3都出隊(duì)列，此時(shí)front = 3，在將a6插入隊(duì)列，此時(shí)rear = 6。

此時(shí)，隊(duì)列長(zhǎng)度為3，隊(duì)列未滿，再將a7插入隊(duì)列時(shí)，就會(huì)報(bào)錯(cuò)數(shù)組越界，但是此時(shí)數(shù)組空間未滿，前面0、1、2都空著，這種現(xiàn)象稱為“假溢出”。

雖然這種方法不用移動(dòng)元素，但是卻造成空間上的浪費(fèi)?？梢钥闯龃藭r(shí)數(shù)組是還有空間去容納新元素a7的，因此我們需要將前面浪費(fèi)的空間重新利用起來(lái)，減少空間的浪費(fèi)，這就是循環(huán)隊(duì)列的意義所在了。

1.循環(huán)隊(duì)列包括兩個(gè)指針(其實(shí)就是兩個(gè)整數(shù)型變量，因?yàn)樵谶@里有指示作用，所以這里理解為指針)， front 指針指向隊(duì)頭元素， rear 指針指向隊(duì)尾元素的下一個(gè)位置。

2.rear和front互相追趕著，這個(gè)追趕過(guò)程就是隊(duì)列添加和刪除的過(guò)程，如果rear追到head說(shuō)明隊(duì)列滿了，如果front追到rear說(shuō)明隊(duì)列為空。

3,rear和front位置的移動(dòng)，關(guān)鍵在于% (取模運(yùn)算)，這樣就防止rear和front 超過(guò)maxsize。

網(wǎng)上最?？吹降膶?shí)現(xiàn)代碼

class SqQueue(object):
    def __init__(self, maxsize):
        self.queue = [None] * maxsize
        self.maxsize = maxsize
        self.front = 0
        self.rear = 0
    # 返回當(dāng)前隊(duì)列的長(zhǎng)度
    def QueueLength(self):
        return (self.rear - self.front + self.maxsize) % self.maxsize
    # 如果隊(duì)列未滿，則在隊(duì)尾插入元素，時(shí)間復(fù)雜度O(1)
    def EnQueue(self, data):
        if (self.rear + 1) % self.maxsize == self.front:
            print("The queue is full!")
        else:
            self.queue[self.rear] = data
           # self.queue.insert(self.rear,data)
            self.rear = (self.rear + 1) % self.maxsize
    # 如果隊(duì)列不為空，則刪除隊(duì)頭的元素,時(shí)間復(fù)雜度O(1)
    def DeQueue(self):
        if self.rear == self.front:
            print("The queue is empty!")
        else:
            data = self.queue[self.front]
            self.queue[self.front] = None
            self.front = (self.front + 1) % self.maxsize
            return data
    # 輸出隊(duì)列中的元素
    def ShowQueue(self):
        for i in range(self.maxsize):
            print(self.queue[i],end=',')
        print(' ')

這有個(gè)bug，由于 self.rear = (self.rear + 1) % self.maxsize 這會(huì)造成一個(gè)空間的浪費(fèi)??！可以運(yùn)行下代碼看看。

所以自己寫(xiě)了一段代碼，直接使用現(xiàn)有元素個(gè)數(shù)cnt 與 maxsize 比較來(lái)判斷是否為空？是否已滿？

class CycleQueue(object):
    def __init__(self, maxsize):
        self.queue = [None] * maxsize
        self.maxsize = maxsize
        self.front = 0
        self.rear = 0
        self.cnt = 0
    def is_empty(self):
        return self.cnt == 0
    def is_full(self):
        return self.cnt == self.maxsize
    def push(self, val):
        if self.is_full():
            print("The queue is full!")
            return
        if self.is_empty():
            self.queue[self.rear] = val
            self.cnt += 1
        else:
            self.rear = (self.rear + 1) % self.maxsize
            self.queue[self.rear] = val
            self.cnt += 1
    def pop(self):
        if self.is_empty():
            print("The queue is empty!")
            return
        val = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % self.maxsize
        self.cnt -= 1
        return val
    def travel(self):
        travel_list = [self.queue[(self.front + i) % self.maxsize] for i in range(self.cnt)]
        print(travel_list)
    def size(self):
        return self.cnt
if __name__ == '__main__':
    CycleQueue = CycleQueue(6)
    CycleQueue.push('a1')
    CycleQueue.push('a2')
    CycleQueue.push('a3')
    CycleQueue.push('a4')
    CycleQueue.push('a5')
    CycleQueue.travel()  # ['a1', 'a2', 'a3', 'a4', 'a5']
    CycleQueue.push('a6')
    CycleQueue.travel()  # ['a1', 'a2', 'a3', 'a4', 'a5', 'a6']
    CycleQueue.pop()
    CycleQueue.push('a7')
    CycleQueue.travel()  # ['a2', 'a3', 'a4', 'a5', 'a6', 'a7']
    CycleQueue.pop()
    CycleQueue.pop()
    CycleQueue.push('a8')
    CycleQueue.travel()  # ['a4', 'a5', 'a6', 'a7', 'a8']

到此這篇關(guān)于Python常用隊(duì)列全面詳細(xì)梳理的文章就介紹到這了,更多相關(guān)Python常用隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: