棧（stack）又名堆棧斋配，它是一種運算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運算灌闺。這一端被稱為棧頂艰争，相對地，把另一端稱為棧底桂对。向一個棧插入新元素又稱作進(jìn)棧甩卓、入棧或壓棧蕉斜，它是把新元素放到棧頂元素的上面逾柿，使之成為新的棧頂元素；從一個棧刪除元素又稱作出椪耍或退棧机错，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素父腕。
椚醴耍可以用來在函數(shù)調(diào)用的時候存儲斷點，做遞歸時要用到棧璧亮，其基本模型如下：
image
在python中已經(jīng)有實現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)萧诫，在queue庫中的LifoQueue就是一種堆棧斥难，堆棧的實現(xiàn)也是線性表，在Python的queue中是通過列表這一線性順序表實現(xiàn)的帘饶，其LifoQueue源碼如下：
class LifoQueue(Queue):
'''Variant of Queue that retrieves most recently added entries first.'''
def _init(self, maxsize):
self.queue = []
def _qsize(self):
return len(self.queue)
def _put(self, item):
self.queue.append(item)
def _get(self):
return self.queue.pop()
下面我們實現(xiàn)一個自定義的堆棧結(jié)構(gòu)哑诊，首先定義一個堆棧類：
class Stack:
"""堆棧結(jié)構(gòu)類"""
def __init__(self):
self._item = []
接著我們實現(xiàn)基本的方法：添加元素、彈出棧頂及刻、返回棧頂镀裤、判斷是否為空、返回堆棧大小提茁。
class Stack:
"""堆棧結(jié)構(gòu)類"""
def __init__(self):
self._item = []
def push(self, item):
"""
添加新元素
:param item:
:return:
"""
self._item.append(item)
@property
def size(self):
"""
返回堆棧大小
:return:
"""
return len(self._item)
@property
def is_empty(self):
"""
判斷是否為空
:return:
"""
return not self._item
def pop(self):
"""
彈出棧頂元素
:return:
"""
return self._item.pop()
def peek(self):
"""
返回棧頂元素
:return:
"""
return self._item[-1]
上面實現(xiàn)的只是基礎(chǔ)模型淹禾，缺少異常處理和其他相關(guān)的機(jī)制，用列表實現(xiàn)堆棧茴扁，安全性不是很高铃岔，但是如果使用鏈表使用的話一次只能按序獲取一個元素，從鏈表一端到另一端峭火，這樣安全性會更高毁习。
image
