建站
咨詢
售后
建站咨詢
新聞中心
1 棧的概念
棧由一系列對(duì)象對(duì)象組織的一個(gè)集合，這些對(duì)象的增加和刪除操作都遵循一個(gè)“后進(jìn)先出”（Last In First Out，LIFO）的原則。
創(chuàng)新互聯(lián)公司專業(yè)提供成都西信服務(wù)器托管服務(wù)，為用戶提供五星數(shù)據(jù)中心、電信、雙線接入解決方案，用戶可自行在線購(gòu)買成都西信服務(wù)器托管服務(wù)，并享受7*24小時(shí)金牌售后服務(wù)。
在任何時(shí)刻只能向棧中插入一個(gè)對(duì)象，但只能取得或者刪除只能在棧頂進(jìn)行。比如由書構(gòu)成的棧，唯一露出封面的書就是頂部的那本，為了拿到其他的書，只能移除壓在上面的書，如圖：
棧的實(shí)際應(yīng)用
實(shí)際上很多應(yīng)用程序都會(huì)用到棧，比如：
- 網(wǎng)絡(luò)瀏覽器將最近瀏覽的網(wǎng)址存放在一個(gè)棧中。每當(dāng)用戶訪問(wèn)者訪問(wèn)一個(gè)新網(wǎng)站時(shí)，這個(gè)新網(wǎng)站的網(wǎng)址就被壓入棧頂。這樣，每當(dāng)我們?cè)跒g覽器單擊"后退"按鈕時(shí)（或者按鍵盤快捷鍵 ，大部分撤銷快捷鍵），就可以彈出當(dāng)前最近一次訪問(wèn)的網(wǎng)址，以回到其先前訪問(wèn)的瀏覽狀態(tài)。CTRL+Z
- 文本編輯器通常會(huì)提供一個(gè)"撤銷"機(jī)制以取消最近的編輯操作并返回到先前狀態(tài)。這個(gè)撤銷操作也是通過(guò)將文本的變化狀態(tài)保存在一個(gè)棧中得以實(shí)現(xiàn)。
- 一些高級(jí)語(yǔ)言的內(nèi)存管理，JVM 的棧、Python 棧還用于內(nèi)存管理、嵌套語(yǔ)言特性的運(yùn)行時(shí)環(huán)境等
- 回溯（玩游戲，尋找路徑，窮舉搜索）
- 在算法中使用，如漢諾塔、樹形遍歷、直方圖問(wèn)題，也用于圖算法，如拓?fù)渑判?/li>
語(yǔ)法處理：
- 參數(shù)和局部變量的空間是用堆棧在內(nèi)部創(chuàng)建的。編譯器對(duì)大括號(hào)匹配的語(yǔ)法檢查對(duì)遞歸的支持在編譯器中像后綴或前綴一樣的表達(dá)式
2 棧的抽象數(shù)據(jù)類型
任何數(shù)據(jù)結(jié)構(gòu)都離不開數(shù)據(jù)的保存和獲得方式，如前所述，棧是元素的有序集合，添加和操作與移除都發(fā)生在其頂端（棧頂），那么它的抽象數(shù)據(jù)類型包括：
- Stack():創(chuàng)建一個(gè)空棧，它不需要參數(shù)，且會(huì)返回一個(gè)空棧
- push(e)：將一個(gè)元素 e 添加到棧 S 的棧頂，它需要一個(gè)參數(shù) e，且無(wú)返回值
- pop(): 將棧頂端的元素移除，它不需要參數(shù)，但會(huì)返回頂端的元素，并且修改棧的內(nèi)容
- top(): 返回棧頂端的元素，但是并不移除棧頂元素；若棧為空，這個(gè)操作會(huì)操作
- is_empty(): 如果棧中不包含任何元素，則返回一個(gè)布爾值True
- size()：返回棧中元素的數(shù)據(jù)。它不需要參數(shù)，且會(huì)返回一個(gè)整數(shù)。在 Python 中，可以用 這個(gè)特殊方法實(shí)現(xiàn)。__len__
Python 棧的大小可能是固定的，也可能有一個(gè)動(dòng)態(tài)的實(shí)現(xiàn)，即允許大小變化。在大小固定棧的情況下，試圖向已經(jīng)滿的棧添加一個(gè)元素會(huì)導(dǎo)致棧溢出異常。同樣，試圖從一個(gè)已經(jīng)是空的棧中移除一個(gè)元素，進(jìn)行 操作這種情況被稱為下溢。pop()
3 用 Python 的列表實(shí)現(xiàn)棧
在學(xué)習(xí) Python 的時(shí)候，一定學(xué)過(guò) Python 列表 ， 它能通過(guò)一些內(nèi)置的方式實(shí)現(xiàn)棧的功能：list
- 通過(guò) 方法用于添加一個(gè)元素到列表尾部，這種方式就能模擬 操作appendpush()
- 通過(guò) 方法用于模擬出棧操作pop()
- 通過(guò) 模擬 操作L[-1]top()
- 通過(guò)判斷 模擬 操作len(L)==0isEmpty()
- 通過(guò) 函數(shù)實(shí)現(xiàn) 函數(shù)len()size()
代碼如下：
class ArrayStack:
""" 通過(guò) Python 列表實(shí)現(xiàn) LIFO 棧"""
def __init__(self):
self._data = []
def size(self):
""" return the number of elements in the stack"""
return len(self._data)
def is_empty(self):
""" return True if the stack is empty"""
return len(self._data) == 0
def push(self, e):
""" add element e to the top of the stack"""
self._data.append(e)
def pop(self):
""" remove and return the element from the top of the stack
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data.pop()
def top(self):
"""return the top of the stack
Raise Empty exception if the stack is empty
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data[-1] # the last item in the list
arrayStack = ArrayStack()
arrayStack.push("Python")
arrayStack.push("Learning")
arrayStack.push("Hello")
print("Stack top element: ", arrayStack.top())
print("Stack length: ", arrayStack.size())
print("Stack popped item: %s" % arrayStack.pop())
print("Stack is empty?", arrayStack.is_empty())
arrayStack.pop()
arrayStack.pop()
print("Stack is empty?", arrayStack.is_empty())
# arrayStack.pop()運(yùn)行該程序，結(jié)果：
Stack top element: Hello
Stack length: 3
Stack popped item: Hello
Stack is empty? False
Stack is empty? True除了將列表的隊(duì)尾作為棧頂，也可以通過(guò)將列表的頭部作為棧的頂端。不過(guò)在這種情況下，便無(wú)法直接使用 方法和 方法，但是可以通過(guò) 和 方法顯式地訪問(wèn)下標(biāo)為 0 的元素，即列表的第一個(gè)元素，代碼如下：pop()append()pop()insert()
class ArrayStack:
""" 通過(guò) Python 列表實(shí)現(xiàn) LIFO 棧"""
def __init__(self):
self._data = []
def size(self):
""" return the number of elements in the stack"""
return len(self._data)
def is_empty(self):
""" return True if the stack is empty"""
return len(self._data) == 0
def push(self, e):
""" add element e to the top of the stack"""
self._data.insert(0, e)
def pop(self):
""" remove and return the element from the top of the stack
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data.pop(0)
def top(self):
"""return the top of the stack
Raise Empty exception if the stack is empty
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data[0] # the last item in the list雖然我們改變了抽象數(shù)據(jù)類型的實(shí)現(xiàn)，卻保留了其邏輯特征，這種能力體現(xiàn)了抽象思想。不管，雖然兩種方法都實(shí)現(xiàn)了棧，但兩者的性能方法有差異：
- append() 和 方法的時(shí)間復(fù)雜度都是 _**O(1)**，_常數(shù)級(jí)別操作pop()
- 第二種實(shí)現(xiàn)的性能則受制于棧中的元素個(gè)數(shù)，這是因?yàn)? 和 的時(shí)間復(fù)雜度都是 O(n)，元素越多就越慢。insert(0)pop(0)
4 用 collections.deque 實(shí)現(xiàn)棧
在 Python 中， 模塊有一個(gè)雙端隊(duì)列數(shù)據(jù)結(jié)構(gòu) deque，這個(gè)數(shù)據(jù)結(jié)構(gòu)同樣實(shí)現(xiàn)了 和 方法：collectionsappend()pop()
>>> from collections import deque
>>> myStack = deque()
>>> myStack.append('Apple')
>>> myStack.append('Banana')
>>> myStack.append('Orange')
>>>
>>> myStack
deque(['Apple', 'Banana', 'Orange'])
>>> myStack.pop()
'Orange'
>>> myStack.pop()
'Banana'
>>>
>>> len(myStack)
1
>>> myStack[0]
'Apple'
>>> myStack.pop()
'Apple'
>>>
>>> myStack.pop()
Traceback (most recent call last):
File "", line 1, in
myStack.pop()
IndexError: pop from an empty deque
>>> 為什么有了 list 還需要 deque？
可能你可以看到 deque 和列表 list 對(duì)元素的操作差不多，那么為什么 Python 中有列表還增加了 deque 這一個(gè)數(shù)據(jù)結(jié)構(gòu)呢？
那是因?yàn)?，Python 中的列表建立在連續(xù)的內(nèi)存塊中，意味著列表的元素是緊挨著存儲(chǔ)的。
這對(duì)一些操作來(lái)說(shuō)非常有效，比如對(duì)列表進(jìn)行索引。獲取 的速度很快，因?yàn)?Python 確切地知道在內(nèi)存中尋找它的位置。這種內(nèi)存布局也允許切片在列表上很好地工作。myList[3]
毗連的內(nèi)存布局是 list 可能需要花費(fèi)更多時(shí)間來(lái) 一些對(duì)象。如果連續(xù)的內(nèi)存塊已經(jīng)滿了，那么它將需要獲得另一個(gè)內(nèi)存塊，先將整體 copy 過(guò)去，這個(gè)動(dòng)作可能比一般的 操作花費(fèi)更多的時(shí)間。.append().append()
而雙端隊(duì)列 是建立在一個(gè)雙鏈表的基礎(chǔ)上。在一個(gè)鏈接列表結(jié)構(gòu)中，每個(gè)條目都存儲(chǔ)在它自己的內(nèi)存塊中，并有一個(gè)對(duì)列表中下一個(gè)條目的引用。deque
雙鏈表也是如此，只是每個(gè)條目都有對(duì)列表中前一個(gè)和后一個(gè)條目的引用。這使得你可以很容易地在列表的兩端添加節(jié)點(diǎn)。
在一個(gè)鏈接列表結(jié)構(gòu)中添加一個(gè)新的條目，只需要設(shè)置新條目的引用指向當(dāng)前堆棧的頂部，然后將堆棧的頂部指向新條目。
Memory structure of a deque pushing a new element
然而，這種在棧上不斷增加和刪除條目的時(shí)間是有代價(jià)的。獲取 的速度要比列表慢，因?yàn)?Python 需要走過(guò)列表的每個(gè)節(jié)點(diǎn)來(lái)獲取第三個(gè)元素。myDeque[3]
幸運(yùn)的是，你很少想在棧上做隨機(jī)索引元素或進(jìn)行列表切片操作。棧上的大多數(shù)操作都是 或 。pushpop
如果你的代碼不使用線程，常數(shù)時(shí)間的 和 操作使 deque 成為實(shí)現(xiàn) Python 棧的一個(gè)更好的選擇。.append().pop()
5 用 queue.LifoQueue 實(shí)現(xiàn)棧
Python 棧在多線程程序中也很有用，我們已經(jīng)學(xué)習(xí)了 和 兩種方式。對(duì)于任何可以被多個(gè)線程訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，在多線程編程中，我們不應(yīng)該使用 ，因?yàn)榱斜聿皇蔷€程安全的。deque 的 和 方法是原子性的，意味著它們不會(huì)被不同的線程干擾。listdequelist.append().pop()
因此，雖然使用 deque 可以建立一個(gè)線程安全的 Python 堆棧，但這樣做會(huì)使你自己在將來(lái)被人誤用，造成競(jìng)態(tài)條件。
好吧，如果你是多線程編程，你不能用 來(lái)做堆棧，你可能也不想用 來(lái)做堆棧，那么你如何為一個(gè)線程程序建立一個(gè) Python 堆棧？listdeque
答案就在 模塊中：queue.LifoQueue。還記得你是如何學(xué)習(xí)到棧是按照后進(jìn)先出（LIFO）的原則運(yùn)行的嗎？嗯，這就是 LifoQueue 的 "Lifo "部分所代表的含義。queue
雖然 list 和 deque 的接口相似，但 LifoQueue 使用 和 來(lái)從棧中添加和刪除數(shù)據(jù)。.put().get()
>>> from queue import LifoQueue
>>> stack = LifoQueue()
>>> stack.put('H')
>>> stack.put('E')
>>> stack.put('L')
>>> stack.put('L')
>>> stack.put('O')
>>> stack
>>>
>>> stack.get()
'O'
>>> stack.get()
'L'
>>> stack.empty()
False
>>> stack.qsize()
3
>>> stack.get()
'L'
>>> stack.get()
'E'
>>> stack.qsize()
1
>>> stack.get()
'H'
>>> stack.get_nowait()
Traceback (most recent call last):
File "", line 1, in
stack.get_nowait()
_queue.Empty
>>>
>>> stack.put('Apple')
>>> stack.get_nowait()
'Apple' 與 deque 不同，LifoQueue 被設(shè)計(jì)為完全線程安全的。它的所有方法都可以在線程環(huán)境中安全使用。它還為其操作添加了可選的超時(shí)功能，這在線程程序中經(jīng)常是一個(gè)必須的功能。
然而，這種完全的線程安全是有代價(jià)的。為了實(shí)現(xiàn)這種線程安全，LifoQueue 必須在每個(gè)操作上做一些額外的工作，這意味著它將花費(fèi)更長(zhǎng)的時(shí)間。
通常情況下，這種輕微的減速對(duì)你的整體程序速度并不重要，但如果你已經(jīng)測(cè)量了你的性能，并發(fā)現(xiàn)你的堆棧操作是瓶頸，那么小心地切換到 deque 可能是值得做的。
6 選擇哪一種實(shí)現(xiàn)作為棧
一般來(lái)說(shuō)，如果你不使用多線程，你應(yīng)該使用 。如果你使用多線程，那么你應(yīng)該使用 ，除非你已經(jīng)測(cè)量了你的性能，發(fā)現(xiàn) 和 的速度的小幅提升會(huì)帶來(lái)足夠的差異，以保證維護(hù)風(fēng)險(xiǎn)。dequeLifoQueuepushpop
你可以對(duì)列表可能很熟悉，但需要謹(jǐn)慎使用它，因?yàn)樗锌赡艽嬖趦?nèi)存重新分配的問(wèn)題。和 的接口是相同的，而且 沒有線程不安全問(wèn)題。dequelistdeque
7 總結(jié)
本文介紹了棧這一數(shù)據(jù)結(jié)構(gòu)，并介紹了在現(xiàn)實(shí)生活中的程序中如何使用它的情況。在文章的中，介紹了 Python 中實(shí)現(xiàn)棧的三種不同方式，知道了 對(duì)于非多線程程序是一個(gè)更好的選擇，如果你要在多線程編程環(huán)境中使用棧的話，可以使用 。
網(wǎng)站欄目：Python實(shí)現(xiàn)棧的幾種方式及其優(yōu)劣
文章URL：http://www.5511xx.com/article/dpippsg.html
