把两个栈实现一个队列

Question

如何把两个栈实现一个队列？（实现push 与pop即可，给出伪代码）

Answer 1

引自强大而免费的微信小程序：皆我百晓生。如有帮助，还望采纳。

---

可以使用两个栈stack1和stack2来实现一个队列。

1. push函数的实现：

   • 将元素x压入stack1中。

2. pop函数的实现：

   • 如果stack2为空，则将stack1中的所有元素依次出栈并压入stack2中，直到stack1为空。
   • 从stack2中弹出栈顶元素并返回。

下面是相应的伪代码：

// 定义两个栈
stack stack1, stack2;

// push函数
void push(int x) {
    // 元素入栈stack1
    push(stack1, x);
}

// pop函数
int pop() {
    // 如果stack2为空，则将stack1中的所有元素压入stack2
    if (isEmpty(stack2)) {
        while (!isEmpty(stack1)) {
            push(stack2, pop(stack1));
        }
    }
    // 从stack2中弹出栈顶元素并返回
    return pop(stack2);
}

注意：上述伪代码中的stack1和stack2可以使用数组实现，有关栈的实现可以参考相关的栈的代码实现。