棧是最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)剑肯，但也是最重要的數(shù)據(jù)結(jié)構(gòu)。它出現(xiàn)在很多不同的應(yīng)用中欺旧，在更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法中充當(dāng)工具姑丑。
從形式上，棧支持兩種操作的抽象數(shù)據(jù)類(lèi)型ADT辞友，壓棧和入棧：
- S.push()
- S.pop()
此外栅哀，他還有以下方法： - S.top() 在不移除棧頂元素的前提下，返回棧頂元素踏枣，若棧為空昌屉，則報(bào)錯(cuò)。
- S.is_empty() 如果棧中沒(méi)有元素茵瀑，返回True间驮。
- S.is_empty() 返回棧中元素的個(gè)數(shù)。
初始化棧時(shí)马昨，棧一半為空竞帽，且容量沒(méi)有限制，棧元素可以是任意類(lèi)型鸿捧。
棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)（Last In First Out）——LIFO屹篓。可以聯(lián)想到python的列表匙奴，list.append()堆巧、list.pop()，是現(xiàn)成的方法泼菌〉簦可以直接用。
有了以上信息哗伯，我們就可以開(kāi)始著手實(shí)現(xiàn)一個(gè)棧類(lèi)了荒揣。
這里涉及到一種設(shè)計(jì)模式——適配器模式。python的list類(lèi)可以很方便的實(shí)現(xiàn)棧焊刹，所以我們通過(guò)改編它來(lái)實(shí)現(xiàn)系任。
適配器設(shè)計(jì)模式適用于任何上下文，可以使我們可以有效地使用一個(gè)現(xiàn)有的類(lèi)虐块，以使它的方法能夠與那些與其相關(guān)但又不同的類(lèi)或者接口相匹配俩滥。
通用的使用方法是將一個(gè)包含現(xiàn)存類(lèi)作為一個(gè)新類(lèi)的隱藏域，利用這個(gè)隱藏實(shí)例變量的方法實(shí)現(xiàn)新類(lèi)的方法非凌。
以這種方式應(yīng)用適配器設(shè)計(jì)模式举农，我們已經(jīng)創(chuàng)建了一個(gè)新類(lèi)，可以執(zhí)行一些現(xiàn)有類(lèi)相同的方法敞嗡，但是卻用更加方便的方式進(jìn)行封裝颁糟。
改編列表類(lèi)：
- S.push(e) -------------->L.append(e)
- S.pop(e) -------------->L.pop(e)
- S.top() -------------->L[-1]
- S.is_empty() -------------->len(L)==0
- len(S) -------------->len(L)
我們先定義一個(gè)異常類(lèi)用來(lái)說(shuō)明棧中為空。
class Empty(Exception):
"""Error attempting to access an empty container"""
pass
下面是棧類(lèi)的代碼：
class Empty(Exception):
"""Error attempting to access an empty container"""
pass
class ArrayStack:
"""LIFO Stack using a python list"""
def __init__(self):
self._data = []
def __len__(self):
"""返回棧中的元素個(gè)數(shù)"""
return len(self._data)
def is_empty(self):
"""如果棧為空喉悴，返回True"""
return len(self._data) == 0
def push(self, e):
"""壓棧"""
return self._data.append(e)
def top(self):
"""返回棧頂元素棱貌，但不返回不彈棧"""
if self.is_empty():
raise Empty('Stack is empty!')
return self._data[-1]
def pop(self):
"""彈出棧頂元素，并返回這個(gè)元素"""
if self.is_empty():
raise Empty('Stack is empty!')
return self._data.pop()
def __str__(self):
return str(self._data)
if __name__ == '__main__':
# 調(diào)用這個(gè)棧
s = ArrayStack()
s.push(1)
s.push(2)
s.push(3)
print(s)
print('len(s)', len(s))
print('s.top()',s.top())
s.pop()
print(s)
print('s.pop()',s.pop())
print('len(s)', len(s))
s.push(5)
s.push(9)
print(s)
print('len(s)', len(s))
我在最下面又加了str()方法箕肃，可以打印棧婚脱，可以方便我們做測(cè)試。
運(yùn)行結(jié)果：
