说到“先进后出”,很多人第一反应就是:这不就是栈吗?其实没错,先进后出(First In, Last Out,简称FILO)正是栈这种数据结构最核心的特性。
栈到底是个什么东西?
你可以把栈想象成一摞盘子。你往上面放盘子,只能从顶部放;取的时候也只能从顶部开始拿。最早放进去的那个盘子,被压在最底下,想拿它,得先把上面所有的盘子都拿走才行。这就是典型的“先进后出”。
在程序里,栈也是一样的逻辑。数据按顺序压入(push),但取出(pop)时必须从最后进入的那个开始。你不能跳过中间元素直接访问底部的数据。
代码里的栈长什么样?
比如用Python简单实现一个栈:
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def is_empty(self):
return len(self.items) == 0
# 使用示例
s = Stack()
s.push("A")
s.push("B")
s.push("C")
print(s.pop()) # 输出 C
print(s.pop()) # 输出 B
print(s.pop()) # 输出 A
你看,A最先进,最后出;C最后进,最先出。完全符合“先进后出”的规则。
栈在实际开发中怎么用?
浏览器的返回按钮就是一个经典例子。你从首页点进详情页,再跳到设置页,每一步都被压进一个“页面栈”。点击返回时,系统不是随机跳转,而是按栈的规则,一步步从最近的页面往外弹。这就是为什么你不会突然跳回三个月前访问过的某个页面。
再比如函数调用。main函数调用func1,func1又调用func2,这些函数会被压进调用栈。只有func2执行完,才能回到func1,最后回到main。如果中间发生错误导致栈溢出,程序就会崩溃,也就是常说的“爆栈”。
那所有“先进后出”的都是栈吗?
反过来理解也很重要。只要满足“先进后出”这一条,不管底层怎么实现,都可以看作是栈的应用。比如你用微信聊天,撤回功能最多支持两分钟内的一条消息。系统显然不会把所有历史消息都缓存着,而是只保留最近几条,新的来了就顶掉旧的——这本质上就是一个时间上的栈结构。
所以,“先进后出”是栈的本质特征,而栈是实现这一行为最常见的方式。两者基本可以划等号,尤其是在计算机科学语境下。