asp美食网站源码,网站 工商备案,广告设计与制作培训,网站建设义乌目录 一、栈的基本概念 1.栈的概念 2.入栈 入栈的步骤 3.出栈 出栈的步骤 4.获取栈顶元素 获取栈顶元素的步骤 二、 Python中的栈 顺序表实现 链表实现 三、栈的实战 1.LCR 123. 图书整理 I 思路与算法 2.LCR 027. 回文链表 思路与算法 3.1614. 括号的最大嵌套深度 思路与算法 … 目录 一、栈的基本概念 1.栈的概念 2.入栈 入栈的步骤 3.出栈 出栈的步骤 4.获取栈顶元素 获取栈顶元素的步骤 二、 Python中的栈 顺序表实现 链表实现 三、栈的实战 1.LCR 123. 图书整理 I 思路与算法 2.LCR 027. 回文链表 思路与算法 3.1614. 括号的最大嵌套深度 思路与算法 四、栈的应用 轻舟快船祝你好过春山 —— 25.3.3 一、栈的基本概念
1.栈的概念 栈是仅限在表尾进行插入和删除的线性表它遵循后进先出(Last-In-First-OutLIFO)的原则。栈可以类比为一叠盘子你只能访问顶部的盘子而添加或删除盘子只能在顶部进行。在计算机科学中栈通常用于实现函数调用、递归、表达式求值 等操作。我们一般可以用 顺序表 或者 链表 来实现栈。 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 emptyreturn self.data.pop()# 获取栈顶元素 直接相当于列表的索引[-1]操作def top(self):if self.empty():return Stach is emptyreturn 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(fTop element: {stack.top()})print(fSize of stack: {stack.size()})print(fPopped element: {stack.pop()})print(fSize 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 emptyval self.head.valself.head self.head.nextself.len - 1return val# 获取栈顶元素 相当于直接返回链表的头节点def top(self):if self.empty():return Stach is emptyreturn 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(fTop element: {stack.top()})print(fSize of stack: {stack.size()})print(fPopped element: {stack.pop()})print(fSize 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, val0, nextNone):
# 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, val0, nextNone):
# 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 四、栈的应用
在打开界面的情况下打开了一个子界面关闭子界面一开始打开的界面还在
打开界面的操作是将界面放在一个栈中关闭界面的操作就是将界面从栈中移出来关闭的永远是栈顶部的界面也就是所谓的 “栈顶” 元素 栈是一个先进后出的数据结构
