【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) == 0 def 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 = val self.next = None class Stack: def __init__(self): self.head = None self.len = 0 # 入栈操作 直接相当于链表的头插法 def push(self, val): new_node = Node(val) new_node.next = self.head self.head = new_node self.len += 1 # 出栈操作 def pop(self): if self.empty(): return "St ack is empty" val = self.head.val self.head = self.head.next self.len -= 1 return val # 获取栈顶元素 相当于直接返回链表的头节点 def top(self): if self.empty(): return "Stach is empty" return self.head.val def size(self): return self.len def empty(self): return self.len == 0 def 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.next while 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 = head while tmp != None: Stack.append(tmp.val) tmp = tmp.next while head: if head.val != Stack.pop(): return False head = head.next return 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 <= 100s 由数字 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 = 0 res = 0 for x in s: if x == "(": top += 1 res = max(res, top) elif x == ")": top -= 1 return res

---

四、栈的应用

在打开界面的情况下，打开了一个子界面，关闭子界面，一开始打开的界面还在

打开界面的操作是将界面放在一个栈中，关闭界面的操作就是将界面从栈中移出来，关闭的永远是栈顶部的界面，也就是所谓的 “栈顶” 元素

栈是一个先进后出的数据结构