python雙端隊列，[轉載] Python的雙端隊列deque

參考鏈接： Python中的雙端隊列DeQue

python雙端隊列？Python的強大并不在于它的語法，而在于它的庫，當你對各種數據結構感到苦惱時，Python提供了各種開箱即用的數據結構。?

數據結構中最常講授的數據結構有棧、隊列、雙端隊列。?

stl雙端隊列為。棧是一種特殊的線性表，它只允許在一端進行插入、刪除操作，這一端被稱為棧頂（top），另一端則被稱為棧底（bottom）。?

從棧頂插入一個元素被稱為進棧，將一個元素插入棧頂被稱為“壓入棧”，對應的英文說法為push。?

隊列是限制只能在表的一端、從棧頂刪除一個元素被稱為出棧，將一個元素從棧頂刪除被稱為“彈出棧”，對應的英文說法為pop。對于棧而言，最先入棧的元素位于棧底，只有等到上面所有元素出棧之后，棧底的元素才能出棧。因此棧是一種后進先出（LIFO）的線性表。?

圖1為棧的操作示意圖。? 隊列也是一種特殊的線性表，它只允許在表的前端（front）進行刪除操作，只允許在表的后端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。?

對于一個隊列來說，每個元素總是從隊列的rear端進入隊列，然后等待該元素之前的所有元素出隊之后，當前元素才能出隊。因此，把隊列簡稱為先進先出（FIFO）的線性表。?

隊列的示意如圖2所示。? 雙端隊列（即此處介紹的deque）代表一種特殊的隊列，它可以在兩端同時進行插入、刪除操作，如圖3所示。? 對于雙端隊列，由于它可以從兩端分別進入插入、刪除操作，如果程序將所有的插入、刪除操作固定在一端進行，這個雙端隊列就變成前面介紹的棧；如果固定在一端只添加元素、在另一端只刪除元素，那它就是隊列，因此，deque既可當成隊列使用，也可當成棧使用。?

deque位于collections包下，在交互式解釋器中先導入collections包，然后輸入[e for e in dir(collections.deque) if not e.startswith(’_’)]來查看deque的全部方法，可看到如下輸出。?

>>> from collections import deque

>>> [e for e in dir(deque) if not e.startswith('_')]

['append', 'appendleft', 'clear', 'copy', 'count', 'extend', 'extendleft', 'index', 'insert', 'maxlen', 'pop', 'popleft', 'remove', 'reverse', 'rotate']

?

從上面方法可以看出，deque的方法基本都有兩個版本，這就體現了它作為雙端隊列的特征。deque的左邊（left）就相當于它的隊列頭（front）、右邊（right）就相當于它的隊列尾（rear）。?

?append和appendleft：在deque的右邊或左邊添加元素；也就是默認在隊列尾添加元素。? pop和popleft：在deque的右邊或左邊彈出元素；也就是默認在隊列尾彈出元素。? extend和extendleft：在deque的右邊或左邊添加多元素；也就是默認在隊列尾添加多個元素。??

deque中clear()方法用法清空隊列，insert()方法則是線性表的方法，用于在指定位置插入元素。?

假如程序要把deque當成棧使用，意味著只在一端添加、刪除元素，因此調用append和pop方法即可。例如如下代碼。?

'''

遇到問題沒人解答？小編創建了一個Python學習交流QQ群：857662006?

尋找有志同道合的小伙伴，互幫互助,群里還有不錯的視頻學習教程和PDF電子書！

'''

from collections import deque

stack = deque(('Kotlin', 'Python'))

# 元素入棧

stack.append('Erlang')

stack.append('Swift')

print('stack中的元素：' , stack)

# 元素出棧，后添加的元素先出棧

print(stack.pop())

print(stack.pop())

print(stack)

?

運行上面程序，可看到如下結果。?

stack中的元素：deque(['Kotlin', 'Python', 'Erlang', 'Swift'])

Swift

Erlang

deque(['Kotlin', 'Python'])

?

從上面運行結果可以看出：程序最后入棧的元素’Swift’最先出棧，這體現了棧的LIFO的特征。?

假如程序需要把deque當成隊列使用，意味著一端只是用來添加元素，另一端只是用于刪除元素，因此調用append、popleft方法組合即可。例如如下代碼。?

'''

遇到問題沒人解答？小編創建了一個Python學習交流QQ群：857662006?

尋找有志同道合的小伙伴，互幫互助,群里還有不錯的視頻學習教程和PDF電子書！

'''

from collections import deque

?

q = deque(('Kotlin', 'Python'))

# 元素加入隊列

q.append('Erlang')

q.append('Swift')

print('q中的元素：' , q)

# 元素出隊列，先添加的元素先出隊列

print(q.popleft())

print(q.popleft())

print(q)

?

運行上面程序，可看到如下結果。?

q中的元素：deque(['Kotlin', 'Python', 'Erlang', 'Swift'])

Kotlin

Python

deque(['Erlang', 'Swift'])

?

從上面運行結果可以看出：程序先添加的元素’Kotlin’最先出隊列，這體現了棧的FIFO的特征。?

此外，deque還有一個rotate()方法，該方法的作用是將隊列的隊尾元素移動到隊頭來，使之首尾相連。例如如下程序。?

'''

遇到問題沒人解答？小編創建了一個Python學習交流QQ群：857662006?

尋找有志同道合的小伙伴，互幫互助,群里還有不錯的視頻學習教程和PDF電子書！

'''

from collections import deque

?

q = deque(range(5))

print('q中的元素：' , q)

# 執行旋轉，使之首尾相連

q.rotate()

print('q中的元素：' , q)

# 再次執行旋轉，使之首尾相連

q.rotate()

print('q中的元素：' , q)

-------------------------------------------

運行上面程序，可以看到如下輸出。

q中的元素：deque([0, 1, 2, 3, 4])

q中的元素：deque([4, 0, 1, 2, 3])

q中的元素：deque([3, 4, 0, 1, 2])

?

從上面程序運行結果來看，每次執行rotate()方法，deque的隊尾元素都會被移到隊頭，這樣就形成了首尾相連的效果。