【Python 數據結構 5.棧】

目錄

一、棧的基本概念

1.棧的概念

2.入棧

入棧的步驟

3.出棧

出棧的步驟

4.獲取棧頂元素

獲取棧頂元素的步驟

二、 Python中的棧

順序表實現

鏈表實現

三、棧的實戰

1.LCR 123. 圖書整理 I

思路與算法

2.LCR 027. 回文鏈表

思路與算法

3.1614. 括號的最大嵌套深度

思路與算法

四、棧的應用

輕舟快船，祝你好過春山

????????????????????????????????—— 25.3.3

一、棧的基本概念

1.棧的概念

????????棧是僅限在表尾進行插入和刪除的線性表，它遵循后進先出(Last-In-First-Out，LIFO)的原則。棧可以類比為一疊盤子，你只能訪問頂部的盤子，而添加或刪除盤子只能在頂部進行。在計算機科學中，棧通常用于實現：函數調用、遞歸、表達式求值等操作。我們一般可以用順序表或者鏈表來實現棧。

2.入棧

????????棧元素的插入操作叫做入棧，也可稱為進棧、壓棧。直接將元素添加到棧的頂部即可。這個操作類似于將盤子添加到疊盤子的頂部。

入棧的步驟

第1步：將元素壓入棧中，并將棧頂指針或索引指向新的棧頂元素。

第2步：棧的大小增加了 1，頂部元素為剛剛入棧的元素。

3.出棧

????????棧元素的刪除操作叫做出棧，也可稱為彈棧。直接將棧的頂部元素刪除即可。這個操作類似于將疊盤子的頂部的盤子拿走的過程。

出棧的步驟

第1步：將棧頂元素刪除掉，并將棧頂指針或索引指向新的頂元素。

第2步：棧的大小減小了 1。

4.獲取棧頂元素

????????返回棧頂元素的值，無論是鏈表還是順序表，都可以通過棧頂指針在 O(1) 的時間復雜度獲取到棧頂元素。

獲取棧頂元素的步驟

第1步：利用棧頂指針獲取棧頂元素，由于是查詢操作，所以不會改變棧本身的數據

二、 Python中的棧

順序表實現

class Stack:def __init__(self):self.data = []# 入棧操作 直接相當于列表的append操作def push(self, val):self.data.append(val)# 出棧操作 直接相當于列表的pop操作def pop(self):if self.empty():return "Stach is empty"return self.data.pop()# 獲取棧頂元素 直接相當于列表的索引[-1]操作def top(self):if self.empty():return "Stach is empty"return self.data[-1]def size(self):return len(self.data)def empty(self):return len(self.data) == 0def test():stack = Stack()stack.push(1)stack.push(2)stack.push(3)stack.push(4)while not stack.empty():print(f'Top element: {stack.top()}')print(f'Size of stack: {stack.size()}')print(f'Popped element: {stack.pop()}')print(f'Size of stack: {stack.size()}')print("————————————————————————————")
test()

鏈表實現

class Node:def __init__(self, val):self.val = valself.next = Noneclass Stack:def __init__(self):self.head = Noneself.len = 0# 入棧操作 直接相當于鏈表的頭插法def push(self, val):new_node = Node(val)new_node.next = self.headself.head = new_nodeself.len += 1# 出棧操作def pop(self):if self.empty():return "St ack is empty"val = self.head.valself.head = self.head.nextself.len -= 1return val# 獲取棧頂元素 相當于直接返回鏈表的頭節點def top(self):if self.empty():return "Stach is empty"return self.head.valdef size(self):return self.lendef empty(self):return self.len == 0def test():stack = Stack()stack.push(1)stack.push(2)stack.push(3)stack.push(4)while not stack.empty():print(f'Top element: {stack.top()}')print(f'Size of stack: {stack.size()}')print(f'Popped element: {stack.pop()}')print(f'Size of stack: {stack.size()}')print("————————————————————————————")
test()

三、棧的實戰

1.LCR 123. 圖書整理 I

書店店員有一張鏈表形式的書單，每個節點代表一本書，節點中的值表示書的編號。為更方便整理書架，店員需要將書單倒過來排列，就可以從最后一本書開始整理，逐一將書放回到書架上。請倒序返回這個書單鏈表。

示例 1：
輸入：head = [3,6,4,1]輸出：[1,4,6,3]
提示：

0 <= 鏈表長度 <= 10000

思路與算法

Ⅰ、棧的使用：代碼中使用了棧（Stack）這一數據結構。棧的特點是“后進先出”（LIFO），即最后入棧的元素會最先出棧。利用這一特性，可以將鏈表中的值依次壓入棧中，然后再依次彈出，從而實現反轉的效果。

Ⅱ、遍歷鏈表：代碼首先通過一個?while?循環遍歷鏈表，將每個節點的值?head.val?壓入棧中。遍歷結束后，棧中存儲了鏈表所有節點的值，且順序與鏈表中的順序相反。

Ⅲ、反轉并生成結果：接著，代碼通過另一個?while?循環將棧中的元素依次彈出，并追加到結果列表?res?中。由于棧的 LIFO 特性，彈出的順序與壓入的順序相反，因此?res?中的元素順序與鏈表中的順序相反，實現了反轉的效果。?

Ⅳ、返回結果：最后，代碼返回?res，即反轉后的鏈表值列表。

列表.append()：用于在列表的末尾添加一個元素。它會直接修改原列表，而不是返回一個新的列表。

參數名	說明	是否必填
`element`	要添加到列表末尾的元素	是

列表.pop()：用于從列表中移除并返回指定索引處的元素。如果不指定索引，默認移除并返回最后一個元素。

參數名	說明	是否必填
`index`	要移除的元素的索引（從0開始）	否

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseBookList(self, head: Optional[ListNode]) -> List[int]:# 用Python實現數據結構——棧Stack = []res = []while head != None:Stack.append(head.val)head = head.nextwhile len(Stack) > 0:res.append(Stack.pop())return res

2.LCR 027. 回文鏈表

給定一個鏈表的?頭節點?head?，請判斷其是否為回文鏈表。

如果一個鏈表是回文，那么鏈表節點序列從前往后看和從后往前看是相同的。

示例 1：
輸入: head = [1,2,3,3,2,1]
輸出: true
示例 2：
輸入: head = [1,2]
輸出: false
提示：

鏈表 L 的長度范圍為?[1, 105]
0?<= node.val <= 9?

思路與算法

Ⅰ、使用棧存儲鏈表的值：首先，函數通過遍歷鏈表，將每個節點的值依次壓入棧?Stack?中。由于棧是“后進先出”的數據結構，因此棧中存儲的節點順序是鏈表節點值的逆序。

Ⅱ、比較鏈表與棧中的值：接著，函數再次遍歷鏈表，同時從棧中彈出元素，將鏈表節點的值與棧中彈出的值進行比較。如果所有值都匹配，則鏈表是回文鏈表；否則，鏈表不是回文鏈表。

列表.append()：用于在列表的末尾添加一個元素。它會直接修改原列表，而不是返回一個新的列表。

參數名	說明	是否必填
`element`	要添加到列表末尾的元素	是

列表.pop()：用于從列表中移除并返回指定索引處的元素。如果不指定索引，默認移除并返回最后一個元素。

參數名	說明	是否必填
`index`	要移除的元素的索引（從0開始）	否

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def isPalindrome(self, head: ListNode) -> bool:# 列表逆序也可以用棧Stack = []tmp = headwhile tmp != None:Stack.append(tmp.val)tmp = tmp.nextwhile head:if head.val != Stack.pop():return Falsehead = head.nextreturn True

3.1614. 括號的最大嵌套深度

給定?有效括號字符串?s，返回?s?的?嵌套深度。嵌套深度是嵌套括號的?最大?數量。

示例 1：

輸入：s = "(1+(2*3)+((8)/4))+1"

輸出：3

解釋：數字 8 在嵌套的 3 層括號中。

示例 2：

輸入：s = "(1)+((2))+(((3)))"

輸出：3

解釋：數字 3 在嵌套的 3 層括號中。

示例 3：

輸入：s = "()(())((()()))"

輸出：3

提示：

1 <= s.length <= 100
s?由數字?0-9?和字符?'+'、'-'、'*'、'/'、'('、')'?組成
題目數據保證括號字符串?s?是?有效的括號字符串

思路與算法

初始化：top?初始化為 0，表示當前嵌套深度為 0。res?初始化為 0，用于記錄最大嵌套深度。

遍歷字符串：對于字符串中的每個字符?x：如果?x?是 "("，表示進入一個新的嵌套層級，因此?top?增加 1，并更新?res?為?max(res, top)，以確保?res?始終記錄最大深度。如果?x?是?")"，表示退出當前嵌套層級，因此?top?減少 1。

返回結果：遍歷結束后，res?即為字符串中嵌套括號的最大深度。

class Solution:def maxDepth(self, s: str) -> int:top = 0res = 0for x in s:if x == "(":top += 1res = max(res, top)elif x == ")":top -= 1return res

四、棧的應用

在打開界面的情況下，打開了一個子界面，關閉子界面，一開始打開的界面還在

打開界面的操作是將界面放在一個棧中，關閉界面的操作就是將界面從棧中移出來，關閉的永遠是棧頂部的界面，也就是所謂的 “棧頂” 元素

棧是一個先進后出的數據結構