棧是一種線性數(shù)據(jù)結(jié)構(gòu)，用先進(jìn)后出或者是后進(jìn)先出的方式存儲(chǔ)數(shù)據(jù)，棧中數(shù)據(jù)的插入刪除操作都是在棧頂端進(jìn)行，常見(jiàn)棧的函數(shù)操作包括

empty() ? 返回棧是否為空 ? Time Complexity : O(1) size() ? 返回棧的長(zhǎng)度 ? Time Complexity : O(1) top() ? 查看棧頂元素 ? Time Complexity : O(1) push(g) ? 向棧頂添加元素 ? Time Complexity : O(1) pop() ? 刪除棧頂元素 ? Time Complexity : O(1)

python中棧可以用以下三種方法實(shí)現(xiàn)：

１）list

２）collections.deque

３）queue.LifoQueue

使用列表實(shí)現(xiàn)棧

python的內(nèi)置數(shù)據(jù)結(jié)構(gòu)list可以用來(lái)實(shí)現(xiàn)棧，用append()向棧頂添加元素, pop() 可以以后進(jìn)先出的順序刪除元素

但是列表本身有一些缺點(diǎn)，主要問(wèn)題就是當(dāng)列表不斷擴(kuò)大的時(shí)候會(huì)遇到速度瓶頸．列表是動(dòng)態(tài)數(shù)組，因此往其中添加新元素而沒(méi)有空間保存新的元素時(shí)，它會(huì)自動(dòng)重新分配內(nèi)存塊，并將原來(lái)的內(nèi)存中的值復(fù)制到新的內(nèi)存塊中．這就導(dǎo)致了一些append()操作會(huì)消耗更多的時(shí)間

>>> stack = []>>> #append() fuction to push... #element in list... >>> stack.append(’hello’)>>> stack.append(’world’)>>> stack.append(’!’)>>> print(’Initial stack’)Initial stack>>> print(stack)[’hello’, ’world’, ’!’]>>> #pop() function to pop element... #from stack in LIFO order... >>> print(’nElement poped from stack’)Element poped from stack>>> print(stack.pop())!>>> print(stack.pop())world>>> print(stack.pop())hello>>> print(’nStack after all elements are poped’)Stack after all elements are poped>>> print(stack)[]使用collections.deque實(shí)現(xiàn)棧

python中棧也可以用deque類實(shí)現(xiàn)，當(dāng)我們想要在實(shí)現(xiàn)在容器兩端更快速地進(jìn)行append和pop操作時(shí)，deque比列表更合適．deque可以提供O(1)時(shí)間的append和pop操作，而列表則需要O(n)時(shí)間.

>>> from collections import deque>>> stack = deque()>>> # append() fuction to push... #element in list... >>> stack.append(’hello’)>>> stack.append(’world’)>>> stack.append(’!’)>>> print(’Initial stack’)Initial stack>>> print(stack)deque([’hello’, ’world’, ’!’])>>> #pop() function to pop element... #from stack in LIFO order... >>> print(’nElement poped from stack’)Element poped from stack>>> print(stack.pop())!>>> print(stack.pop())world>>> print(stack.pop())hello>>> print(’nStack after all elements are poped’)Stack after all elements are poped>>> print(stack)deque([])使用queue module實(shí)現(xiàn)棧

Queue模塊有LIFO queue，也就是棧結(jié)構(gòu)．用put()和get()操作從Queue中添加和獲得數(shù)據(jù)

>>> from queue import LifoQueue>>> stack = LifoQueue(maxsize = 3)>>> print(stack.qsize())0>>> stack.put(’hello’)>>> stack.put(’world’)>>> stack.put(’!’)>>> print(’nElement poped from stack’)Element poped from stack>>> print(stack.get())!>>> print(stack.get())world>>> print(stack.get())hello>>> print(’nEmpty:’, stack.empty())Empty: True

以上就是python中實(shí)現(xiàn)棧的三種方法的詳細(xì)內(nèi)容，更多關(guān)于python 實(shí)現(xiàn)棧的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！