1舱呻、棧
1.1、棧的基本介紹
??棧(Stack)是一個項(xiàng)的有序集合悠汽。添加項(xiàng)和移除項(xiàng)都發(fā)生在同一“端”箱吕。這一端通常被稱為 頂，另一端的頂部被稱為 底柿冲。
??棧的 底 是有標(biāo)志性的茬高，因?yàn)榇鎯υ跅Ｖ懈拷?底 的項(xiàng)就是棧中儲存時間最長的項(xiàng)。最新添加的項(xiàng)在移除項(xiàng)時也會第一個被移除姻采。這種排序原則有時也稱為LIFO法雅采，也就是 后進(jìn)先出 爵憎。
??棧很重要慨亲，因?yàn)樗鼈兛梢杂糜诜崔D(zhuǎn)項(xiàng)的順序。如下圖所示：
1.2宝鼓、棧的Python實(shí)現(xiàn)
本文采用Python語言中的列表（list）這種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)棧刑棵。首先定義一個 Stack 類，類中包含 進(jìn)棧愚铡、出棧蛉签、棧是否為空、棧的大小 等基本方法沥寥，具體代碼如下：
class Stack():
def __init__(self):
self.stack = []
# 進(jìn)棧
def push(self, item):
self.stack.append(item)
# 出棧
def pop(self):
if self.is_empty() == True:
return None
else:
return self.stack.pop()
# 棧是否為空
def is_empty(self):
return self.stack == []
# 棧的大小
def size(self):
return len(self.stack)
2碍舍、隊(duì)列
2.1、隊(duì)列的基本介紹
??隊(duì)列(Queue)是一系列有順序的元素的集合邑雅，新元素的加入在隊(duì)列的一端片橡，這一端叫做 隊(duì)尾 (rear)，已有元素的移除發(fā)生在隊(duì)列的另一端淮野，叫做 隊(duì)首 (front)捧书。當(dāng)一個元素被加入到隊(duì)列之后，它就從隊(duì)尾開始向隊(duì)首前進(jìn)骤星，直到它成為下一個即將被移出隊(duì)列的元素经瓷。
??最新被加入的元素必須處于隊(duì)尾，在隊(duì)列停留最長時間的元素處于隊(duì)首洞难。這種原則有時候叫做 先進(jìn)先出 (FIFO, first-in first-out)舆吮，進(jìn)出隊(duì)列的過程如下圖所示：
2.2、隊(duì)列的Python實(shí)現(xiàn)
本文采用Python語言中的列表（list）這種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列。首先定義一個 Queue 類歪泳，類中包含 進(jìn)隊(duì)萝勤、出隊(duì)、隊(duì)列是否為空呐伞、隊(duì)列的大小 等基本方法敌卓，具體代碼如下：
class Queue():
def __init__(self):
self.queue = []
# 進(jìn)隊(duì)
def push(self, item):
self.queue.append(item)
# 出隊(duì)
def pop(self):
if self.is_empty() == True:
return None
else:
return self.queue.pop(0)
# 隊(duì)列是否為空
def is_empty(self):
return self.queue == []
# 隊(duì)列的長度
def size(self):
return len(self.queue)
備注：Python中的 collections 模塊中實(shí)現(xiàn)了隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，可以直接調(diào)用伶氢。
