文章目錄

• • 棧的概念
  • 棧的特點
  • 棧的操作
  • Python 實現(xiàn)棧
  • 棧的簡單應(yīng)用：括號匹配問題
  • 棧的簡單應(yīng)用：倒序輸出一組元素

---

棧的概念

棧（stack）又名堆棧，棧是一種線性數(shù)據(jù)結(jié)構(gòu)，用先進后出或者是后進先出的方式存儲數(shù)據(jù)，棧中數(shù)據(jù)的插入刪除操作都是在棧的頂端進行，這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

---

棧的特點

元素后進先出（Last in First Out，LIFO）

---

棧的操作

• push(item)：進棧（向棧頂添加元素）
• pop()：出棧（刪除棧頂元素）
• top()：查看棧頂元素
• empty()：判斷棧是否為空

---

Python 實現(xiàn)棧

棧并不是 Python 的內(nèi)建類型，在必要的時候可以使用列表來模擬基于數(shù)組的棧。如果將列表的末尾看作是棧的頂，列表方法 append() 就是將元素壓入到棧中（進棧），而列表方法 pop() 會刪除并返回棧頂?shù)脑?#xff08;出棧），列表索引的方式 arr[-1] 可以查看棧頂元素。具體代碼實現(xiàn)如下：

class Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if self.empty():return Noneelse:return self.stack.pop()def top(self):if self.empty():return Noneelse:return self.stack[-1]def empty(self):return len(self.stack) == 0

---

棧的簡單應(yīng)用：括號匹配問題

問題描述：

給定一個字符串，字符串中只包含小括號 ()、中括號 []、大括號 {}，求該字符串中的括號是否匹配。匹配規(guī)則：成對出現(xiàn)或者左右對稱出現(xiàn)，例如：

()[]{}：匹配；{[()]}：匹配；({}]：不匹配；()]：不匹配；({)}：不匹配

通過棧來解決：

有字符串 ()[{}]，依次取每個括號，只要是左括號就進棧，只要是右括號就判斷棧頂是否為對應(yīng)的左括號，具體步驟如下：

• ① 遇到左小括號 (，執(zhí)行進棧操作；
• ② 遇到右小括號 )，判斷此時棧頂是否為左小括號 (，是則讓左小括號 ( 出棧，此時棧為空;
• ③ 遇到左中括號 [，執(zhí)行進棧操作；
• ④ 遇到左大括號 {，執(zhí)行進棧操作；
• ⑤ 遇到右大括號 }，判斷此時棧頂是否為左大括號 {，是則讓左大括號 { 出棧，此時棧為空；
• ⑥ 遇到右中括號 ]，判斷此時棧頂是否為左中括號 [，是則讓左中括號 [ 出棧，此時棧為空；
• ⑦ 判斷最終的棧是否為空，是則表示匹配，不是則表示不匹配。其中第 ② ⑤ ⑥ 步中，若判斷為不是，則直接表示不匹配。

Python 代碼實現(xiàn)：

class Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if self.empty():return Noneelse:return self.stack.pop()def top(self):if self.empty():return Noneelse:return self.stack[-1]def empty(self):return len(self.stack) == 0def brackets_match(s):match_dict = {'}': '{', ']': "[", ')': '('}stack = Stack()for ch in s:if ch in ['(', '[', '{']: # 如果為左括號，則執(zhí)行進棧操作stack.push(ch)else: # 如果為右括號if stack.empty(): # 如果棧為空，則不匹配，即多了一個右括號，沒有左括號匹配return Falseelif stack.top() == match_dict[ch]: # 如果棧頂?shù)脑貫閷?yīng)的左括號，則讓棧頂出棧stack.pop()else: # 如果棧頂元素不是對應(yīng)的左括號，則不匹配return Falseif stack.empty(): # 最后的棧如果為空，則匹配，否則不匹配return Trueelse:return Falseprint(brackets_match('[{()}(){()}[]({}){}]')) print(brackets_match('()[{}]')) print(brackets_match('({)}')) print(brackets_match('[]}'))

輸出結(jié)果：

True True False False

---

棧的簡單應(yīng)用：倒序輸出一組元素

把元素存入棧，再順序取出：

class Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if self.empty():return Noneelse:return self.stack.pop()def top(self):if self.empty():return Noneelse:return self.stack[-1]def empty(self):return len(self.stack) == 0def reverse_list(s):stack = Stack()for ch in s:stack.push(ch)new_list = []while not stack.empty():new_list.append(stack.pop())return new_listprint(reverse_list(['A', 'B', 'C', 'D', 'E']))

輸出結(jié)果：

['E', 'D', 'C', 'B', 'A']

總結(jié)

以上是生活随笔為你收集整理的Python 数据结构之栈的实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。