一、栈的基本定义
栈(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. 栈不支持随机访问,只能从栈顶往下遍历。
五、总结
本文详细介绍了栈的定义、操作、应用及其优缺点,栈是一种非常重要和实用的数据结构,广泛应用于计算机科学领域。