【数据结构与算法】栈算法题

**栈算法题**

###什么是栈？

栈是一种线性数据结构，它遵循后进先出（LIFO）的原则。也就是说，最后添加的元素将首先被移除。

### 栈的基本操作栈有以下几个基本操作：

* **push**: 将一个元素添加到栈顶。
* **pop**: 移除栈顶元素。
* **peek**: 查看栈顶元素，但不移除。
* **isEmpty**: 检查栈是否为空。

### 栈的应用栈有很多应用，例如：

* **表达式求值**: 使用栈可以很方便地实现表达式求值。
* **回溯算法**: 栈可以用来存储函数的参数和返回值。
* **括号匹配**: 使用栈可以很容易地检查括号是否匹配。

### 栈的实现我们可以使用数组或链表来实现栈。下面是使用数组实现栈的示例代码：

class Stack:
 def __init__(self, max_size):
 self.max_size = max_size self.stack = [None] * max_size self.top = -1 def push(self, item):
 if self.top == self.max_size -1:
 print("Stack is full.")
 return self.top +=1 self.stack[self.top] = item def pop(self):
 if self.top == -1:
 print("Stack is empty.")
 return None item = self.stack[self.top]
 self.stack[self.top] = None self.top -=1 return item def peek(self):
 if self.top == -1:
 print("Stack is empty.")
 return None return self.stack[self.top]

 def isEmpty(self):
 return self.top == -1# 测试栈的基本操作stack = Stack(5)
print(stack.isEmpty()) # Truestack.push(10)
stack.push(20)
stack.push(30)

print(stack.peek()) #30print(stack.pop()) #30print(stack.pop()) #20print(stack.pop()) #10print(stack.isEmpty()) # True

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

 def push(self, item):
 self.stack.append(item)

 def pop(self):
 return self.stack.pop()

 def isEmpty(self):
 return len(self.stack) ==0def evaluate_expression(expression):
 stack = Stack()
 operators = set(['+', '-', '*', '/'])

 for char in expression:
 if char.isspace():
 continue elif char.isdigit():
 stack.push(int(char))
 elif char in operators:
 operand2 = stack.pop()
 operand1 = stack.pop()
 if char == '+':
 result = operand1 + operand2 elif char == '-':
 result = operand1 - operand2 elif char == '*':
 result = operand1 * operand2 else: # char == '/'
 result = int(operand1 / operand2)
 stack.push(result)

 return stack.pop()


# 测试表达式求值expression = "10 +20 *3 -5"
result = evaluate_expression(expression)
print("Result:", result) # Output: Result:65