栈（Stack）和队列（Queue）是两种基础且重要的线性数据结构，它们在算法设计、系统实现（如函数调用栈、任务调度）中广泛应用

栈Stack和队列Queue是两种基础且重要的线性数据结构它们在算法设计、系统实现如函数调用栈、任务调度中广泛应用。栈Stack特点后进先出LIFO, Last In First Out核心操作push()入栈在栈顶添加元素pop()出栈移除并返回栈顶元素peek()/top()查看栈顶元素不删除isEmpty()判断是否为空实现方式可用数组顺序栈或链表链式栈实现。典型应用括号匹配、表达式求值中缀转后缀、递归模拟、浏览器回退、函数调用栈。队列Queue特点先进先出FIFO, First In First Out核心操作enqueue()入队在队尾添加元素dequeue()出队移除并返回队首元素front()访问队首元素isEmpty()/size()实现方式循环数组避免假溢出、链表链式队列、双端队列Deque等。典型应用广度优先搜索BFS、任务调度、打印任务队列、消息缓冲。⚠️ 注意标准队列仅允许一端入、另一端出而**双端队列Deque**支持两端插入/删除兼具栈与队列特性。# 简单栈实现基于列表classStack:def__init__(self):self.items[]defpush(self,x):self.items.append(x)defpop(self):returnself.items.pop()ifself.itemselseNonedefpeek(self):returnself.items[-1]ifself.itemselseNone# 简单队列实现使用collections.deque高效实现fromcollectionsimportdequeclassQueue:def__init__(self):self.itemsdeque()defenqueue(self,x):self.items.append(x)defdequeue(self):returnself.items.popleft()ifself.itemselseNonedeffront(self):returnself.items[0]ifself.itemselseNone两者时间复杂度在合理实现下均为push/enqueue、pop/dequeue、peek/front→O(1)均摊空间复杂度O(n)n为元素个数。仅用两个栈记为stack_in和stack_out实现一个队列核心思想是利用栈的LIFO特性模拟队列的FIFO行为通过“倒腾”即元素在两栈间转移来保证出队顺序。✅实现原理入队enqueue所有新元素统一压入stack_inO(1)出队dequeue或查看队首front若stack_out为空则将stack_in中所有元素逐个弹出并压入stack_out此时顺序反转原先进入的元素变为栈顶符合FIFO然后从stack_out弹出或查看栈顶元素O(1)若stack_out非空直接操作它O(1) 关键点元素最多被移动一次从stack_in→stack_out因此均摊代价很低。✅Python 示例实现classMyQueue:def__init__(self):self.stack_in[]# 用于入队self.stack_out[]# 用于出队defpush(self,x):self.stack_in.append(x)# O(1)defpop(self):ifnotself.stack_out:whileself.stack_in:# 将in中所有元素倒入out最多执行n次但均摊O(1)self.stack_out.append(self.stack_in.pop())returnself.stack_out.pop()ifself.stack_outelseNone# O(1) 均摊defpeek(self):ifnotself.stack_out:whileself.stack_in:self.stack_out.append(self.stack_in.pop())returnself.stack_out[-1]ifself.stack_outelseNone# O(1) 均摊defempty(self):returnnotself.stack_inandnotself.stack_out# O(1)⏱️时间复杂度分析操作最坏情况均摊时间复杂度说明push()O(1)O(1)直接appendpop()O(n)O(1)倒腾仅在stack_out为空时发生n个元素最多被移动1次 → 总n次操作耗时O(n) ⇒ 均摊O(1)peek()O(n)O(1)同pop均摊分析一致empty()O(1)O(1)仅检查两栈是否为空空间复杂度O(n)存储所有元素每个元素至多同时存在于一个栈中。⚠️ 注意不能每次pop都全量倒腾——必须惰性转移仅当stack_out为空时才倒否则退化为O(n)每次操作。