【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

---

四、栈的应用

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

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

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