个人网站-个人主页作业wordpress 文章去掉时间
目录
一、栈的基本概念
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 <= 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 = 0res = 0for x in s:if x == "(":top += 1res = max(res, top)elif x == ")":top -= 1return res
四、栈的应用
在打开界面的情况下，打开了一个子界面，关闭子界面，一开始打开的界面还在
打开界面的操作是将界面放在一个栈中，关闭界面的操作就是将界面从栈中移出来，关闭的永远是栈顶部的界面，也就是所谓的 “栈顶” 元素
栈是一个先进后出的数据结构