数据结构（王道）——栈的应用

**数据结构（王道）——栈的应用**

栈是一种非常常见的数据结构，它在计算机科学中有着广泛的应用。栈的基本概念是后进先出（LIFO），即最后添加的元素将首先被移除。

**栈的定义和操作**

栈可以用数组或链表来实现，下面我们使用数组来实现一个简单的栈：

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 def size(self):
 return self.top +1

上面的代码实现了一个基本的栈类，支持push、pop、peek、isEmpty和size等操作。

**栈的应用**

栈在计算机科学中有着广泛的应用，下面我们列举一些例子：

### **括号匹配**

栈可以用来检查括号是否匹配。例如，在一个表达式中，如果遇到左括号，则将其压入栈中，如果遇到右括号，则从栈顶取出元素，如果栈为空，则表示括号不匹配。

def is_match(s):
 stack = []
 for c in s:
 if c == '(':
 stack.append(c)
 elif c == ')':
 if not stack or stack.pop() != '(':
 return False return not stackprint(is_match("((()))")) # Trueprint(is_match("(()")) # False

### **表达式求值**

栈可以用来求解表达式的值。例如，在一个逆波兰表达式中，运算符在其对应的操作数之前。

def evaluate(expression):
 stack = []
 operators = set(['+', '-', '*', '/'])
 for token in expression.split():
 if token not in operators:
 stack.append(int(token))
 else:
 operand2 = stack.pop()
 operand1 = stack.pop()
 result = eval(f"{operand1} {token} {operand2}")
 stack.append(result)
 return stack[0]

print(evaluate("34 +")) #7print(evaluate("56 *")) #30

### **回文检测**

栈可以用来检查一个字符串是否是回文。例如，在一个字符串中，如果遇到左括号，则将其压入栈中，如果遇到右括号，则从栈顶取出元素，如果栈为空，则表示字符串是回文。

def is_palindrome(s):
 stack = []
 for c in s:
 if c == ' ':
 continue if c.isalnum():
 stack.append(c)
 else:
 while stack and not stack[-1].isalnum():
 stack.pop()
 if not stack or stack.pop() != c:
 return False return not stackprint(is_palindrome("A man, a plan, a canal: Panama")) # Trueprint(is_palindrome("Not a palindrome")) # False

上面的例子展示了栈在括号匹配、表达式求值和回文检测中的应用。这些例子可以帮助你更好地理解栈的概念及其在计算机科学中的应用。

**总结**

本文介绍了栈的基本概念及其在计算机科学中的应用。我们使用数组来实现一个简单的栈类，并展示了栈在括号匹配、表达式求值和回文检测中的应用。这些例子可以帮助你更好地理解栈的概念及其在计算机科学中的应用。

**参考**

* 《数据结构与算法》王道* 《计算机程序设计艺术》第3 部分：排序和查找以上是关于栈的应用的文章，希望对你有所帮助。