怎么利用双栈结构优雅实现一个具备逆序输出的功能队列-java教程-PHP中文网

双栈实现逆序输出队列的核心是延迟反转：inputstack存入队元素，outputstack在逆序输出时按需接收其倒序元素；首次逆序输出时将inputstack全量倒腾至outputstack，之后直接弹出即得原队列逆序序列，均摊时间o(n)，空间o(n)，逻辑清晰高效。

怎么利用双栈结构优雅实现一个具备逆序输出的功能队列

用两个栈（双栈）实现一个能逆序输出的队列，核心在于“延迟反转”——不急着把所有元素翻转，而是在需要逆序输出时才借助第二个栈完成翻转。这样既保持入队高效（O(1)），又让逆序输出变成一次性的、可复用的操作。

结构设计：inputStack 与 outputStack 各司其职

定义两个栈：

inputStack：专门接收新入队元素，保持原始插入顺序（底→顶 = 先入→后入）；
outputStack：仅在需要逆序输出时被填充，其栈顶即为最早入队的元素（底→顶 = 后入→先入，即原队列的逆序）。

注意：outputStack 不用于日常出队，只服务于“逆序输出”这一特定功能；常规队列的 front()/dequeue() 可仍由 inputStack 直接支持（若要求 FIFO 出队，则需额外中转逻辑，但本题聚焦“逆序输出”，故不强制模拟完整 FIFO 行为）。

逆序输出：一次性倒腾 + 顺序弹出

调用逆序输出时，只需确保 outputStack 包含 inputStack 的全部元素且顺序反转。操作步骤如下：

Reachout.ai

一款面向销售团队的 AI 视频触达与营销工具，通过个性化视频内容辅助企业开展客户开发和销售沟通，提高潜在客户触达效率。

下载

若 outputStack 为空，将 inputStack 中所有元素逐个 pop → push 到 outputStack；
此时 outputStack 栈顶是第一个入队的元素，依次 pop 即得逆序输出序列（即原队列从头到尾的反向）；
后续再次逆序输出时，只要 outputStack 还有剩余元素，可直接继续 pop，无需重复倒腾（惰性优化）。

例如：入队顺序为 [1, 2, 3, 4]，inputStack 自底向上为 [1,2,3,4]；倒腾后 outputStack 自底向上为 [4,3,2,1]，栈顶是 1 —— 弹出顺序即 1→2→3→4，正是原队列的逆序。

代码骨架（Python 风格示意）

无需复杂类封装，几行逻辑即可体现优雅：

input_stack = []
output_stack = []
<p>def enqueue(x):
input_stack.append(x)</p><p>def reverse_output():
if not output_stack:
while input_stack:
output_stack.append(input_stack.pop())</p><h1>此时 output_stack 从顶到底 = 原队列从头到尾</h1><pre class="brush:java;toolbar:false;">result = []
while output_stack:
    result.append(output_stack.pop())
return result

调用 reverse_output() 返回的就是逆序序列（如 [4,3,2,1]），且多次调用会持续清空 outputStack，如需保留或支持迭代式输出，可改用生成器或分离“准备”与“消费”步骤。