一、栈的基本定义
栈(Stack)是一种线性数据结构，它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后入栈的数据最先弹出)。栈可以简单地看做是一种限制性的单向链表，它限制了只能在链表的一端进行插入和删除操作，这一端称之为栈顶(top)，另一端称之为栈底(bottom)。
二、栈的操作
对栈的操作主要有两个：压入和弹出。在栈中压入元素的操作称为push，而弹出元素的操作称为pop。
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
# 压入元素
self.stack.append(item)
def pop(self):
# 弹出元素
if not self.is_empty():
return self.stack.pop()
def peek(self):
# 返回栈顶元素
if not self.is_empty():
return self.stack[-1]
def size(self):
# 返回栈大小
return len(self.stack)
def is_empty(self):
# 判断栈是否为空
return len(self.stack) == 0
三、栈的应用
1. 表达式求值
栈可以用来求表达式的值，由于表达式的优先级问题，我们需要把中缀表达式转化为后缀表达式。比如a+b*c-d，可以转化为abc*+d-
def evaluate_postfix_expression(expression: str) -> int:
stack = Stack()
for i in expression:
if i.isdigit():
stack.push(i)
else:
num2, num1 = int(stack.pop()), int(stack.pop())
if i == '+':
stack.push(num1 + num2)
elif i == '-':
stack.push(num1 - num2)
elif i == '*':
stack.push(num1 * num2)
elif i == '/':
stack.push(num1 / num2)
return stack.pop()
2. 括号匹配
栈也可以用来匹配括号，比如，判断括号序列是否合法，(()())合法，(()非法。
def is_valid_brackets(s: str) -> bool:
stack = Stack()
for i in s:
if i == '(':
stack.push(i)
elif i == ')':
if stack.is_empty():
return False
else:
stack.pop()
return stack.is_empty()
3. 函数调用的系统栈
函数的调用关系也可以看做是一种栈的结构，每当一个函数被调用时，系统就会在栈顶记录下来当前的函数调用信息，同时栈指针上移一位，而在一个函数执行完以后，栈顶的函数返回并弹出，此时系统将把执行权向下移交给当前的栈顶函数。
四、栈的优缺点
1. 优点
1. 栈能够保证基本操作的时间复杂度为O(1)。
2. 栈是一种先进后出的数据结构，特别适用于需要倒序输出或倒序执行操作的场景。
3. 栈可以解决一些复杂的问题，比如函数调用等。
2. 缺点
1. 栈的空间固定，一旦栈满就不能再去push数据，容易产生栈溢出的问题。
2. 栈的操作受限，只有栈顶元素可以进行操作，其他位置的元素不能进行操作。
3. 栈不支持随机访问，只能从栈顶往下遍历。
五、总结
本文详细介绍了栈的定义、操作、应用及其优缺点，栈是一种非常重要和实用的数据结构，广泛应用于计算机科学领域。
原创文章，作者：KIMHZ，如若转载，请注明出处：https://www.506064.com/n/368605.html
微信扫一扫 
支付宝扫一扫 