栈
栈(Stack) 是一种经典的数据结构,它具有“后进先出”(Last-In-First-Out,LIFO)的特性。栈一般有两个根本操作:压栈(Push)和弹栈(Pop)。压栈操作将数据元素增加到栈顶,弹栈操作将栈顶的元素弹出。
除了根本操作,栈还有其他几个重要的概念:
-
栈顶(Top):栈中终究一个压入的元素。
-
栈底(Bottom):栈中最早被压入的元素。
-
栈空(Empty):栈中没有任何元素。
-
栈满(Full):栈中现已没有剩余的空间能够容纳新的元素。
栈的应用非常广泛,常见的应用场景包含:
-
程序的函数调用仓库:每个函数的参数和回来值都被存储在一个栈帧(Stack Frame)中,调用一个函数时就将其栈帧压入栈中,函数回来时再将其栈帧弹出。
-
表达式求值:将中缀表达式转换为后缀表达式,再运用栈来求解后缀表达式。
-
修改器的吊销和重做操作:运用两个栈,一个栈用于存储前史修改操作,另一个栈用于存储已吊销的操作。
-
浏览器的前进和撤退操作:运用两个栈,一个栈用于存储已拜访过的页面,另一个栈用于存储现已拜访过的页面的前一个页面。
栈的完结方式有多种,常见的完结方式包含数组完结和链表完结。数组完结的栈具有随机拜访的特性,但刺进和删去操作的时刻杂乱度较高;链表完结的栈具有刺进和删去操作的时刻杂乱度较低,但拜访元素的时刻杂乱度较高。
Python中能够运用列表(List)来完结栈的功用,由于列表能够在末尾增加和删去元素,能够很方便地完结栈的压入和弹出操作。
以下是运用列表完结栈的根本操作:
- 创建一个空的栈:
stack = []
- 将元素压入栈中:
stack.append(element)
- 从栈中弹出一个元素:
element = stack.pop()
- 获取栈顶元素:
element = stack[-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.
提示:
- −231<=val<=231−1-2^{31}<= val <= 2^{31}- 1
-
pop
、top
和getMin
操作总是在非空栈上调用 -
push
,pop
,top
, andgetMin
最多被调用3∗1043 * 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:
输入: 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
中的每一个字符:
-
假如栈不为空,而且栈顶的括号和当时字符能够匹配,则弹出栈顶的括号。
-
假如栈为空,或许栈顶的括号和当时字符不能匹配,则将当时字符压入栈中。
终究,假如栈为空,阐明一切的括号都匹配了,回来 True
;不然回来 False
。
150. 逆波兰表达式求值
给你一个字符串数组tokens
,表明一个依据逆波兰表明法表明的算术表达式。
请你核算该表达式。回来一个表明表达式值的整数。
留意:
- 有用的算符为
'+'
、'-'
、'*'
和'/'
。 - 每个操作数(运算目标)都能够是一个整数或许另一个表达式。
- 两个整数之间的除法总是向零截断。
- 表达式中不含除零运算。
- 输入是一个依据逆波兰表明法表明的算术表达式。
- 答案及一切中间核算成果能够用32 位整数表明。
示例1:
输入: tokens = [“2″,”1″,”+”,”3″,”*”]
输出: 9
解说: 该算式转化为常见的中缀算术表达式为:((2+1)∗3)=9((2 + 1) * 3) = 9
示例2:
输入: tokens = [“4″,”13″,”5″,”/”,”+”]
输出: 6
解说: 该算式转化为常见的中缀算术表达式为:(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((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<=1041 <= 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
-
界说一个栈,一个字符串变量res用来保存当时解码的成果,一个整数变量mul用来保存当时数字字符所表明的倍数;
-
遍历字符串s中的每个字符c:
a. 假如c是数字字符,将其参加mul变量的个位上;
b. 假如c是左括号字符,将当时的mul和res入栈,并分别将mul和res初始化为0和空字符串;
c. 假如c是右括号字符,弹出栈顶的mul和res,并将当时的res设置为栈顶的res加上mul个当时的res;
d. 假如c是其他字符,直接将其参加res中;
-
终究回来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∗1051 <= 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
-
初始化 ans 和 num 为 0,sign 为 1,stack 为 [sign]。
-
遍历字符串 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,开端下一个数字的解析。
-
-
终究,将 ans 与终究一个数字 num 乘以当时环境的符号 sign 相乘的成果相加,得到终究的核算成果。
需求留意的是,这个完结并没有考虑乘除法的优先级,只是依照从左到右的顺序进行核算。假如需求考虑优先级,能够在遍历时将乘除法的成果先核算出来,再核算加减法的成果。