建站
咨詢
售后
建站咨詢
新聞中心
在“數(shù)據(jù)結(jié)構(gòu)”課程中最常講授的數(shù)據(jù)結(jié)構(gòu)有棧、隊列、雙端隊列。
站在用戶的角度思考問題，與客戶深入溝通，找到田陽網(wǎng)站設(shè)計與田陽網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗，讓設(shè)計與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：做網(wǎng)站、網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣、申請域名、虛擬主機、企業(yè)郵箱。業(yè)務(wù)覆蓋田陽地區(qū)。
棧是一種特殊的線性表，它只允許在一端進行插入、刪除操作，這一端被稱為棧頂（top），另一端則被稱為棧底（bottom）。
從棧頂插入一個元素被稱為進棧，將一個元素插入棧頂被稱為“壓入?！?，對應(yīng)的英文說法為 push；相應(yīng)地，從棧頂刪除一個元素被稱為出棧，將一個元素從棧頂刪除被稱為“彈出棧”，對應(yīng)的英文說法為 pop。
對于棧而言，最先入棧的元素位于棧底，只有等到上面所有元素都出棧之后，棧底的元素才能出棧。因此棧是一種后進先出（LIFO）的線性表。如圖 1 所示為棧的操作示意圖。
隊列也是一種特殊的線性表，它只允許在表的前端（front）進行刪除操作，在表的后端（rear）進行插入操作。進行插入操作的端被稱為隊尾，進行刪除操作的端被稱為隊頭。
對于一個隊列來說，每個元素總是從隊列的 rear 端進入隊列的，然后等待該元素之前的所有元素都出隊之后，當(dāng)前元素才能出隊。因此，隊列是一種先進先出（FIFO）的線性表。隊列示意圖如圖 2 所示。
雙端隊列（即此處介紹的 deque）代表一種特殊的隊列，它可以在兩端同時進行插入、刪除操作，如圖 3 所示。
對于一個雙端隊列來說，它可以從兩端分別進行插入、刪除操作，如果程序?qū)⑺械牟迦?、刪除操作都固定在一端進行，那么這個雙端隊列就變成了棧；如果固定在一端只添加元素，在另一端只刪除元素，那么它就變成了隊列。因此，deque 既可被當(dāng)成隊列使用，也可被當(dāng)成棧使用。
deque 位于 collections 包下，在交互式解釋器中先導(dǎo)入 collections 包，然后輸入 [e for e in dir(collections.deque) if not e.startswith('_')] 命令來查看 deque 的全部方法，可以看到如下輸出結(jié)果：
>>> 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 的方法基本都有兩個版本，這就體現(xiàn)了它作為雙端隊列的特征。deque 的左邊（left）就相當(dāng)于它的隊列頭（front），右邊（right）就相當(dāng)于它的隊列尾（rear）：
append 和 appendleft：在 deque 的右邊或左邊添加元素，也就是默認在隊列尾添加元素。
pop 和 popleft：在 deque 的右邊或左邊彈出元素，也就是默認在隊列尾彈出元素。
extend 和 extendleft：在 deque 的右邊或左邊添加多個元素，也就是默認在隊列尾添加多個元素。
deque 中的 clear() 方法用于清空隊列：insert() 方法則是線性表的方法，用于在指定位置插入元素。
假如程序要把 deque 當(dāng)成棧使用，則意味著只在一端添加、刪除元素，因此調(diào)用 append 和 pop 方法即可。例如如下程序：
從上面的方法可以看出，deque 的方法基本都有兩個版本，這就體現(xiàn)了它作為雙端隊列的特征。deque 的左邊（left）就相當(dāng)于它的隊列頭（front），右邊（right）就相當(dāng)于它的隊列尾（rear）：
append 和 appendleft：在 deque 的右邊或左邊添加元素，也就是默認在隊列尾添加元素。
pop 和 popleft：在 deque 的右邊或左邊彈出元素，也就是默認在隊列尾彈出元素。
extend 和 extendleft：在 deque 的右邊或左邊添加多個元素，也就是默認在隊列尾添加多個元素。
deque 中的 clear() 方法用于清空隊列：insert() 方法則是線性表的方法，用于在指定位置插入元素。
假如程序要把 deque 當(dāng)成棧使用，則意味著只在一端添加、刪除元素，因此調(diào)用 append 和 pop 方法即可。例如如下程序：
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)運行上面程序，可以看到如下運行結(jié)果：
stack中的元素： deque(['Kotlin', 'Python', 'Erlang', 'Swift']) Swift Erlang deque(['Kotlin', 'Python'])
從上面的運行結(jié)果可以看出，程序最后入棧的元素“Swift”最先出棧，這體現(xiàn)了棧的 LIFO 的特征。
假如程序要把 deque 當(dāng)成隊列使用，則意味著一端只用來添加元素，另一端只用來刪除元素，因此調(diào)用 append、popleft 方法即可。例如如下程序：
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)運行上面程序，可以看到如下運行結(jié)果：
q中的元素： deque(['Kotlin', 'Python', 'Erlang', 'Swift']) Kotlin Python deque(['Erlang', 'Swift'])
從上面的運行結(jié)果可以看出，程序先添加的元素“Katlin”最先出隊列，這體現(xiàn)了隊列的 FIFO 的特征。
此外，deque 還有一個 rotate() 方法，該方法的作用是將隊列的隊尾元素移動到隊頭，使之首尾相連。例如如下程序：
from collections import deque
q = deque(range(5))
print('q中的元素：' , q)
# 執(zhí)行旋轉(zhuǎn)，使之首尾相連
q.rotate()
print('q中的元素：' , q)
# 再次執(zhí)行旋轉(zhuǎn)，使之首尾相連
q.rotate()
print('q中的元素：' , q)運行上面程序，可以看到如下輸出結(jié)果：
q中的元素： deque([0, 1, 2, 3, 4]) q中的元素： deque([4, 0, 1, 2, 3]) q中的元素： deque([3, 4, 0, 1, 2])
從上面的輸出結(jié)果來看，每次執(zhí)行 rotate() 方法，deque 的隊尾元素都會被移到隊頭，這樣就形成了首尾相連的效果。
文章名稱：創(chuàng)新互聯(lián)Python教程：Pythonqueue雙端隊列模塊及用法
鏈接分享：http://www.dlmjj.cn/article/coiggcd.html
