首页 > 其他分享 >栈 | stack ?

栈 | stack ?

时间：2023-06-17 11:38:40浏览次数：48  
标签：示例 res self pop stack 表达式

栈

栈（Stack） 是一种经典的数据结构，它具有“后进先出”（Last-In-First-Out，LIFO）的特性。栈通常有两个基本操作：压栈（Push）和弹栈（Pop）。压栈操作将数据元素添加到栈顶，弹栈操作将栈顶的元素弹出。

除了基本操作，栈还有其他几个重要的概念：

  1. 栈顶（Top）：栈中最后一个压入的元素。

  2. 栈底（Bottom）：栈中最先被压入的元素。

  3. 栈空（Empty）：栈中没有任何元素。

  4. 栈满（Full）：栈中已经没有剩余的空间可以容纳新的元素。

栈的应用非常广泛，常见的应用场景包括：

  1. 程序的函数调用堆栈：每个函数的参数和返回值都被存储在一个栈帧（Stack Frame）中，调用一个函数时就将其栈帧压入栈中，函数返回时再将其栈帧弹出。

  2. 表达式求值：将中缀表达式转换为后缀表达式，再使用栈来求解后缀表达式。

  3. 编辑器的撤销和重做操作：使用两个栈，一个栈用于存储历史编辑操作，另一个栈用于存储已撤销的操作。

  4. 浏览器的前进和后退操作：使用两个栈，一个栈用于存储已访问过的页面，另一个栈用于存储已经访问过的页面的前一个页面。

栈的实现方式有多种，常见的实现方式包括数组实现和链表实现。数组实现的栈具有随机访问的特性，但插入和删除操作的时间复杂度较高；链表实现的栈具有插入和删除操作的时间复杂度较低，但访问元素的时间复杂度较高。

Python中可以使用列表（List）来实现栈的功能，因为列表可以在末尾添加和删除元素，可以很方便地实现栈的压入和弹出操作。

以下是使用列表实现栈的基本操作：

  1. 创建一个空的栈：
stack = []
  1. 将元素压入栈中：
stack.append(element)
  1. 从栈中弹出一个元素：
element = stack.pop()
  1. 获取栈顶元素：
element = stack[-1]
  1. 检查栈是否为空：
if not stack:
    print("stack is empty")

如果不嫌麻烦，可以把栈的实现可以封装成一个类，方便使用。以下是一个简单的栈类的实现：

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, element):
        self.stack.append(element)
    
    def pop(self):
        if not self.stack:
            return None
        return self.stack.pop()
    
    def peek(self):
        if not self.stack:
            return None
        return self.stack[-1]
    
    def is_empty(self):
        return not self.stack

使用这个类，可以很方便地创建栈对象，并使用栈的各种方法：

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 3
print(stack.peek())  # 2
print(stack.is_empty())  # False

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

 

示例 1:

输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]

输出： [null,null,null,null,-3,null,0,-2]

解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

 

提示：

  • $-2^{31} <= val <= 2^{31} - 1$
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 $3 * 10^4$ 次

这个代码很简单，但是要注意题目的要求 “常数时间获得最小值”。 所以用一个辅助最小栈。

class MinStack:

    def __init__(self):
        self.vals = []
        self.minStack = [float('inf')]

    def push(self, val: int) -> None:
        self.vals.append(val)
        self.minStack.append(self.minStack[-1] if self.minStack[-1] < val else val)

    def pop(self) -> None:
        self.vals.pop()
        self.minStack.pop()

    def top(self) -> int:
        return self.vals[-1] 

    def getMin(self) -> int:
        return self.minStack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

 

示例 1：

输入： s = "()" 输出： true

示例 2：

输入： s = "()[]{}" 输出： true

示例 3：

输入： s = "(]" 输出： false

 

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成
class Solution:
    def isValid(self, s: str) -> bool:
        brackets = {'(':')','[':']','{':'}'}
        stack = []
        for x in s:
            if stack and stack[-1] in brackets and brackets[stack[-1]] == x:
                stack.pop()
            else:
                stack.append(x)
        return not len(stack)

首先，定义了一个字典 brackets，用于存储括号的匹配关系。然后创建一个空栈 stack，遍历输入字符串 s 中的每一个字符：

  1. 如果栈不为空，并且栈顶的括号和当前字符可以匹配，则弹出栈顶的括号。

  2. 如果栈为空，或者栈顶的括号和当前字符不能匹配，则将当前字符压入栈中。

最后，如果栈为空，说明所有的括号都匹配了，返回 True；否则返回 False。

150. 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

 

示例 1：

输入： tokens = ["2","1","+","3","*"] 输出： 9 解释： 该算式转化为常见的中缀算术表达式为：$((2 + 1) * 3) = 9$

示例 2：

输入： tokens = ["4","13","5","/","+"] 输出： 6 解释： 该算式转化为常见的中缀算术表达式为：$(4 + (13 / 5)) = 6$

示例 3：

输入： tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"] 输出： 22 解释： 该算式转化为常见的中缀算术表达式为：

$((10 * (6 / ((9 + 3) * -11))) + 17) + 5 \= ((10 * (6 / (12 * -11))) + 17) + 5 \= ((10 * (6 / -132)) + 17) + 5 \= ((10 * 0) + 17) + 5 \= (0 + 17) + 5 \= 17 + 5 \= 22$

提示：

  • $1 <= tokens.length <= 10^4$
  • tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

  • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + *也可以依据次序计算出正确结果。
  • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
class Solution:
    def evalRPN(self, tokens: [str]) -> int:
        nums = []
        for i in tokens:
            if i.isdigit() or len(i)>1:   # 负数用isdigit()返回false
                nums.append(int(i))
            else:
                n1 = nums.pop()
                n2 = nums.pop()
                if i == '+':
                    nums.append(n2+n1)
                elif i == '-':
                    nums.append(n2-n1)
                elif i == '*':
                    nums.append(n2*n1)
                elif i == '/':
                    nums.append(int(n2/n1))
        return nums[-1]

该算法使用一个栈来跟踪表达式中的数字，在从左到右读取tokens时使用。当遇到一个数字时，它被推送到栈上。当遇到运算符时，栈上的前两个数字被弹出，运算符被应用于它们，然后将结果推回到栈上。

在循环结束时，栈上应该只剩下一个数字，这个数字是表达式的最终结果。这个数字作为函数的输出返回。

代码检查每个token以查看它是运算符还是数字。如果它是数字，则将其转换为整数并推送到栈上。如果它是运算符，则弹出栈上的前两个数字，并应用运算符。然后将结果推回到栈上。

代码处理四个运算符：+，-，*和/。如果运算符是+，则将弹出的两个数字相加，并将结果推回到栈上。如果运算符是-，则将第二个弹出的数字从第一个弹出的数字中减去，并将结果推回到栈上。如果运算符是*，则将弹出的两个数字相乘，并将结果推回到栈上。如果运算符是/，则将第二个弹出的数字除以第一个弹出的数字（使用整数除法），并将结果推回到栈上。

最后，函数返回栈中的最后一个元素，这应该是表达式的最终结果。

71. 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/' 。
  • 最后一个目录名（如果存在）不能 以 '/' 结尾。
  • 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

 

示例 1：

输入： path = "/home/"
输出： "/home"
解释： 注意，最后一个目录名后面没有斜杠。

示例 2：

输入： path = "/../" 输出： "/" 解释： 从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

输入： path = "/home//foo/" 输出： "/home/foo" 解释： 在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

输入： path = "/a/./b/../../c/" 输出： "/c"

 

提示：

  • 1 <= path.length <= 3000
  • path 由英文字母，数字，'.'，'/' 或 '_' 组成。
  • path 是一个有效的 Unix 风格绝对路径。
class Solution:
    def simplifyPath(self, path: str) -> str:
        path = path.split('/')
        stack = []
        for i in path:
            if i == '' or i == '.':
                continue
            elif i == '..':
                if stack:
                    stack.pop()
            else:
                stack.append(i)
        return '/' + '/'.join(stack)

用于简化给定的 Unix 路径。它接受一个字符串参数 path，然后使用斜杠 / 分隔路径字符串，并将其存储在一个列表中。然后，代码遍历该列表，并根据以下规则对路径进行简化：

  • 如果当前路径是空字符串或者单点（.），则跳过。
  • 如果当前路径是双点（..），则将栈中的最后一个路径弹出。
  • 如果当前路径不是单点或双点，则将其添加到栈中。

最后，代码使用 join 函数将栈中的路径组合成一个字符串，并在开头添加一个斜杠 /，然后将简化后的路径字符串作为结果返回。

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

 

示例 1：

输入： s = "3[a]2[bc]"
输出： "aaabcbc"

示例 2：

输入： s = "3[a2[c]]"
输出： "accaccacc"

示例 3：

输入： s = "2[abc]3[cd]ef"
输出： "abcabccdcdcdef"

示例 4：

输入： s = "abc3[cd]xyz"
输出： "abccdcdcdxyz"

 

提示：

  • 1 <= s.length <= 30

  • s 由小写英文字母、数字和方括号 '[]' 组成

  • s 保证是一个 有效 的输入。

  • s 中所有整数的取值范围为 [1, 300]

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        res = ''
        mul = 0
        for c in s:
            if c.isdigit():
                mul = mul*10 + int(c)
                # 注意mul的大小
            elif c == '[':
                stack.append([mul,res])
                res = ''
                mul = 0
            elif c == ']':
                m,s = stack.pop()
                res = s + m*res
            else:
                res += c
        return res

  1. 定义一个栈，一个字符串变量res用来保存当前解码的结果，一个整数变量mul用来保存当前数字字符所表示的倍数；

  2. 遍历字符串s中的每个字符c：

    a. 如果c是数字字符，将其加入mul变量的个位上；

    b. 如果c是左括号字符，将当前的mul和res入栈，并分别将mul和res初始化为0和空字符串；

    c. 如果c是右括号字符，弹出栈顶的mul和res，并将当前的res设置为栈顶的res加上mul个当前的res；

    d. 如果c是其他字符，直接将其加入res中；

  3. 最终返回res即为解码结果。

224. 基本计算器 - 力扣（Leetcode）

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval（) 。

 

示例 1：

输入： s = "1 + 1"
输出： 2

示例 2：

输入： s = " 2-1 + 2 "
输出： 3

示例 3：

输入： s = "(1+(4+5+2)-3)+(6+8)"
输出： 23

 

提示：

  • $1 <= s.length <= 3 * 10^5$

  • s 由数字、'+'、'-'、'('、')'、和 ' ' 组成

  • s 表示一个有效的表达式

  • '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)

  • '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)

  • 输入中不存在两个连续的操作符

  • 每个数字和运行的计算将适合于一个有符号的 32位 整数

class Solution:
    def calculate(self, s: str) -> int:
        ans = 0
        num = 0
        sign = 1
        stack = [sign]  # stack[-1]: current env's sign

        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '(':
                stack.append(sign)
            elif c == ')':
                stack.pop()
            elif c == '+' or c == '-':
                ans += sign * num
                sign = (1 if c == '+' else -1) * stack[-1]
                num = 0

        return ans + sign * num

  1. 初始化 ans 和 num 为 0，sign 为 1，stack 为 [sign]。

  2. 遍历字符串 s 中的每个字符 c：

    • 如果 c 是数字，则更新 num 为 num*10 + int(c)。

    • 如果 c 是左括号 (，则将当前的 sign 压入 stack 中，表示进入一个新的环境。

    • 如果 c 是右括号 )，则将 stack 的栈顶元素弹出，得到当前环境的符号 sign_env。将当前环境的结果 num 与当前环境的符号 sign_env 相乘，加入到 ans 中，表示当前环境的结果已经计算完成，可以退出当前环境了。

    • 如果 c 是加号 + 或减号 -，则将当前环境的结果 num 与当前环境的符号 sign_env 相乘，加入到 ans 中。更新当前环境的符号 sign 为 1 或 -1，具体根据 c 的值来判断。同时，将当前环境的符号 sign 与 stack 的栈顶元素相乘，得到当前环境下的符号，更新 stack 的栈顶元素。最后，将 num 重置为 0，开始下一个数字的解析。

  3. 最后，将 ans 与最后一个数字 num 乘以当前环境的符号 sign 相乘的结果相加，得到最终的计算结果。

需要注意的是，这个实现并没有考虑乘除法的优先级，只是按照从左到右的顺序进行计算。如果需要考虑优先级，可以在遍历时将乘除法的结果先计算出来，再计算加减法的结果。

标签：示例,res,self,pop,stack,表达式
From： https://blog.51cto.com/Lolitann/6504568

相关文章

  • 一条新的glibc IO_FILE利用链：_IO_obstack_jumps利用分析
    一条新的glibcIO_FILE利用链：_IO_obstack_jumps利用分析本文首发于[跳跳糖]，仅在个人博客记录。由于跳跳糖的文章无法修改，所以本文有部分不同前言众所周知，由于移除了__malloc_hook/__free_hook/__realloc_hook等等一众hook全局变量，高版本glibc想要劫持程序流，离不开攻击_IO_FIL......
  • stack、vector的使用和特点
    Stack的方法stack是继承VectorclassStackextendsVector特点：栈模式----遍历时元素是先进后出具体代码实现：publicstaticvoidmain(String[]args){ Stack<String>stack=newStack<>(); //将元素添加到栈顶 stack.push("aaa"); stack.push("bbb"); stack......
  • cloudstack的重新封装--api调用
    使用python将cloudstack的多个功能进行重新封装形成api调用。#coding=utf-8#!/usr/bin/envpythonimportbase64importhmacimportjsonimportrequestsimportsysimporttimeimporturllibimportreimporthashlibimportloggingLOG=logging.getLogger(__name__......
  • LiveVideoStackCon 2020上海 6月见
    自强不息，否极泰来。当你在2020年底总结这一年的得失时，LiveVideoStackCon可能保留了难忘的瞬间——我们等待他太久了。原本计划于4月举行的LiveVideoStackCon2020上海由于COVID-19不得不推迟到6月13-14日，LiveVideoStack团队全体远程办公，线下活动全面停摆，并被每周四/周日晚间线上公......
  • LiveVideoStackCon 北京站，好久不见
    LiveVideoStackCon2020北京站定在10月31以及11月1日。在6月的线上峰会也有提过，等到条件允许了，一定要和大家好好聚一聚。后来想了想，再没有比北京的秋天更好的时候了。6号线转14号线，金台路中转站步行距离不超过200米，T恤已经汗湿，微微贴住了前襟后背。 四川人苏辙说“伏中苦热焦皮骨......
  • LiveVideoStackCon2021音视频技术大会北京站开幕在即，精彩抢鲜看
    10.29-10.30，LiveVideoStackCon2021音视频技术大会北京站将在北京丽亭华苑酒店举行。16个技术专题，67场技术分享，77位讲师，近500位多媒体生态技术代表将齐聚本届LiveVideoStackCon。本届大会主题为：新技术，新机会。在此主题下，大会将围绕技术创新和行业机会，为大家带来一场多媒体技术领域......
  • LiveVideoStack Meet | 杭州：CV与流媒体将走向融合
    11月14日，重启后的LiveVideoStackMeet在杭州中国(杭州)5G创新谷举行。由于杭州城市特使周昌印的努力，本次活动突出了计算机视觉相关的话题，这也引出了另一个问题——计算机视觉与流媒体两个领域是否会逐步融合？计算机视觉与流媒体彼此还有比较清晰的界限的，前者是通过计算机对生物视觉......
  • LiveVideoStack年终技术盘点总结
    年终盘点#009#在2021年底，LiveVideoStack策划了一次年终技术盘点，我们向音视频领域的一线技术工作者们发出了约稿邀请，希望他们能够输出一些音视频方向的技术内容。众所周知，年底正是技术人最忙碌的时刻，要写各种总结报告，还要做明年的规划，所以我们并没有对这次约稿抱有很高的期待。但是......
  • 解释内存中的栈(stack)、堆(heap)和方法区(method area)的用法
    对象的属性其实就是数据，存放在堆中；而对象的行为（方法），就是运行逻辑，放在栈中堆区:专门用来保存对象的实例(new创建的对象和数组)，实际上也只是保存对象实例的属性值，属性的类型和对象本身的类型标记等，并不保存对象的方法（方法是指令，保存在Stack中）1.存储的全部是对象，每个对象都包含一个与......
  • 运维工具SaltStack之一安装部署
    一、概述salt是一个异构平台基础设置管理工具，使用轻量级的通讯器ZMQ,用Python写成的批量管理工具，完全开源，遵守Apache2协议，与Puppet，Chef功能类似，有一个强大的远程执行命令引擎，也有一个强大的配置管理系统，通常叫做SaltStateSystem。 二、基本原理采用C/S模式，server端就是salt的mas......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99