栈练习题(逆波兰表达式,有效括号,出入栈次序匹配,最小栈)

**栈相关练习题**

###1. 逆波兰表达式逆波兰表达式是一种特殊的算术表达式，它遵循以下规则：

* 每个操作符都紧跟着它所作用的两个运算数。
* 操作数和操作符之间没有空格。

例如，表达式 `3+4*2` 在逆波兰表示法中变为 `342 * +`。

#### 题目：

给定一个逆波兰表达式，请你实现一个函数来计算它的值。

#### 示例：

输入：`"342 * +"`
输出：`11`

####代码示例：

def evalRPN(expression):
 stack = []
 for token in expression.split():
 if token in "+-*/":
 b = stack.pop()
 a = stack.pop()
 if token == "+":
 stack.append(a + b)
 elif token == "-":
 stack.append(a - b)
 elif token == "*":
 stack.append(a * b)
 else:
 stack.append(a / b)
 else:
 stack.append(int(token))
 return stack[0]

###2.有效括号给定一个字符串，请你判断它是否是有效的括号序列。

#### 题目：

* 左括号必须在右括号之前。
* 每个左括号都必须与一个右括号配对。
* 左括号和右括号的数量必须相等。

#### 示例：

输入：`"(()())"`
输出：`True`

输入：`")("`
输出：`False`

####代码示例：

def isValid(s):
 stack = []
 for c in s:
 if c == "(":
 stack.append(c)
 elif c == ")":
 if not stack or stack.pop() != "(":
 return False return not stack

###3. 出入栈次序匹配给定两个栈，请你判断它们的元素是否按照正确的顺序出栈。

#### 题目：

* 栈1和栈2中的元素必须按照正确的顺序出栈。
* 如果栈1中有多个相同元素，栈2中也必须有相同数量的相同元素。

#### 示例：

输入：`[1,2,3] [4,5,6]`
输出：`True`

输入：`[1,2,3] [4,5]`
输出：`False`

####代码示例：

def validateStackSequences(pushed, popped):
 stack = []
 pop_index =0 for num in pushed:
 stack.append(num)
 while stack and stack[-1] == popped[pop_index]:
 stack.pop()
 pop_index +=1 return not stack

###4. 最小栈给定一个栈，请你实现一个函数来返回最小元素。

#### 题目：

* 每次出栈时，必须返回当前栈中最小的元素。
* 如果栈为空，则返回None。

#### 示例：

输入：`[1,2,3]`
输出：`1`

输入：`[]`
输出：`None`

####代码示例：

class MinStack:
 def __init__(self):
 self.stack = []
 self.min_stack = []

 def push(self, x: int) -> None:
 self.stack.append(x)
 if not self.min_stack or x <= self.min_stack[-1]:
 self.min_stack.append(x)

 def pop(self) -> None:
 self.stack.pop()
 self.min_stack.pop()

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

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

###5. 最大栈给定一个栈，请你实现一个函数来返回最大元素。

#### 题目：

* 每次出栈时，必须返回当前栈中最大的元素。
* 如果栈为空，则返回None。

#### 示例：

输入：`[1,2,3]`
输出：`3`

输入：`[]`
输出：`None`

####代码示例：

class MaxStack:
 def __init__(self):
 self.stack = []
 self.max_stack = []

 def push(self, x: int) -> None:
 self.stack.append(x)
 if not self.max_stack or x >= self.max_stack[-1]:
 self.max_stack.append(x)

 def pop(self) -> None:
 self.stack.pop()
 self.max_stack.pop()

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

 def getMax(self) -> int:
 return self.max_stack[-1]

###6. 最小栈和最大栈给定一个栈，请你实现两个函数来返回最小元素和最大元素。

#### 题目：

* 每次出栈时，必须返回当前栈中最小的元素和最大的元素。
* 如果栈为空，则返回None。

#### 示例：

输入：`[1,2,3]`
输出：`1` 和 `3`

输入：`[]`
输出：`None` 和 `None`

####代码示例：

class MinMaxStack:
 def __init__(self):
 self.stack = []
 self.min_stack = []
 self.max_stack = []

 def push(self, x: int) -> None:
 self.stack.append(x)
 if not self.min_stack or x <= self.min_stack[-1]:
 self.min_stack.append(x)
 if not self.max_stack or x >= self.max_stack[-1]:
 self.max_stack.append(x)

 def pop(self) -> None:
 self.stack.pop()
 self.min_stack.pop()
 self.max_stack.pop()

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

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

 def getMax(self) -> int:
 return self.max_stack[-1]

###7. 最小栈和最大栈（使用两个栈）

给定一个栈，请你实现两个函数来返回最小元素和最大元素。

#### 题目：

* 每次出栈时，必须返回当前栈中最小的元素和最大的元素。
* 如果栈为空，则返回None。

#### 示例：

输入：`[1,2,3]`
输出：`1` 和 `3`

输入：`[]`
输出：`None` 和 `None`

####代码示例：

class MinMaxStack:
 def __init__(self):
 self.stack = []
 self.min_stack = []
 self.max_stack = []

 def push(self, x: int) -> None:
 self.stack.append(x)
 if not self.min_stack or x <= self.min_stack[-1]:
 self.min_stack.append(x)
 if not self.max_stack or x >= self.max_stack[-1]:
 self.max_stack.append(x)

 def pop(self) -> None:
 self.stack.pop()
 self.min_stack.pop()
 self.max_stack.pop()

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

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

 def getMax(self) -> int:
 return self.max_stack[-1]

###8. 最小栈和最大栈（使用一个栈）

给定一个栈，请你实现两个函数来返回最小元素和最大元素。

#### 题目：

* 每次出栈时，必须返回当前栈中最小的元素和最大的元素。
* 如果栈为空，则返回None。

#### 示例：

输入：`[1,2,3]`
输出：`1` 和 `3`

输入：`[]`
输出：`None` 和 `None`

####代码示例：

class MinMaxStack:
 def __init__(self):
 self.stack = []
 self.min_max_stack = []

 def push(self, x: int) -> None:
 self.stack.append(x)
 if not self.min_max_stack or x <= self.min_max_stack[-1]:
 self.min_max_stack.append(x)

 def pop(self) -> None:
 self.stack.pop()
 self.min_max_stack.pop()

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

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

 def getMax(self) -> int:
 return self.min_max_stack[-1]

###9. 最小栈和最大栈（使用一个栈和一个队列）

给定一个栈，请你实现两个函数来返回最小元素和最大元素。

#### 题目：

* 每次出栈时，必须返回当前栈中最小的元素和最大的元素。
* 如果栈为空，则返回None。

#### 示例：

输入：`[1,2,