摘要：队列和栈是数据结构里的“老熟人”，一个“先进先出”，一个“后进先出”，看似性格迥异，却能玩出神奇的组合——用两个栈实现队列的功能。今天就来拆解这个经典问题，附上手把手改写的代码，小白也能轻松看懂。
队列和栈是数据结构里的“老熟人”，一个“先进先出”，一个“后进先出”，看似性格迥异，却能玩出神奇的组合——用两个栈实现队列的功能。今天就来拆解这个经典问题，附上手把手改写的代码，小白也能轻松看懂。
需求很简单：用两个栈（Stack）实现一个队列（Queue），支持push（入队）和pop（出队）操作。
队列特性：先入队的元素必须先出队（比如依次入队a、b、c，出队顺序必须是a→b→c）。栈特性：后入栈的元素先出栈（比如依次入栈a、b、c，出栈顺序是c→b→a）。怎么让两个“后进先出”的栈，凑出一个“先进先出”的队列呢？
入队（push）：所有元素先放进第一个栈（stack1），此时元素顺序是“先进后出”（比如a在栈底，c在栈顶）。出队（pop）：若第二个栈（stack2）为空，就把stack1的所有元素逐个弹出并压入stack2，此时stack2的元素顺序会反转（c在栈底，a在栈顶），正好符合队列的“先进先出”。若stack2不为空，直接弹出栈顶元素（就是最早入队的元素）。举个例子：
入队a→b→c：stack1变成[a, b, c]（a在底，c在顶）。第一次出队：stack2为空，把stack1的元素移到stack2，stack2变成[c, b, a]（c在底，a在顶），弹出a（正确！）。再入队d：直接压入stack1，stack1现在是[d]。第二次出队：stack2还有[b, c]，弹出b（正确！）。#include using namespace std;class QueueWithTwoStacks {private:stack stack1; // 负责接收新元素（入队专用）stack stack2; // 负责输出元素（出队专用）public:// 入队操作：直接把元素压入stack1void push(int element) {stack1.push(element);}// 出队操作：通过stack2反转顺序后弹出int pop {// 步骤1：如果stack2为空，把stack1的所有元素转移过来if (stack2.empty) {while (!stack1.empty) {// 弹出stack1的栈顶元素int topVal = stack1.top;stack1.pop;// 压入stack2，实现顺序反转stack2.push(topVal);}}// 步骤2：弹出stack2的栈顶元素（即最早入队的元素）int frontVal = stack2.top;stack2.pop;return frontVal;}};class QueueWithTwoStacks:def __init__(self):# 初始化两个栈，stack1存新元素，stack2负责出队self.stack1 = self.stack2 = def push(self, element):# 入队：直接追加到stack1self.stack1.append(element)def pop(self):# 出队：先检查stack2是否为空if not self.stack2:# 把stack1的元素倒序移到stack2while self.stack1:self.stack2.append(self.stack1.pop)# 弹出stack2的最后一个元素（栈顶）return self.stack2.pop用两个栈实现队列，本质是利用“两次后进先出”等价于“一次先进先出”的特性。这种“以栈代队”的思路，不仅是面试中的经典考点，更能帮你理解数据结构的灵活性——看似对立的结构，通过巧妙组合就能实现意想不到的功能。下次遇到类似问题，不妨试试这种“反转再反转”的思路哦！
来源：码农世界