【剑指Offer】T9 两个栈实现队列

用两个栈来实现一个队列,完成队列的 Push 和 Pop 操作。 队列中的元素为 int 类型

  • 出栈:
    1. 栈 2 空:(栈一元素到栈二,再栈二出栈)

      • 取栈一的顶
      • push 到栈 2
      • pop 栈一
      • 直到栈一空
      • 栈二出栈
    2. 栈 2 不空:栈二出栈
  • 入栈:栈一 push
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
            
        }
        int temp = stack2.top();
        stack2.pop();
        return temp;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

扩展:两个队列实现栈
https://www.jianshu.com/p/285419bfa880

出栈:

//如果 queueA 的大小不为 0 则循环取出元素
while(queueA.size() > 0){
    //被取出的元素
    int result = queueA.poll();
    // 这里注意我们取出元素后再去判断一次,队列是否为空,如果为空代表是最后一个元素
    if(queueA.size() != 0){
        queueB.add(result)
    }else{
        return result;
    }
}
  • 任何时候两个队列总有一个是空的。
  • 添加元素总是向非空队列中 add 元素。
  • 取出元素的时候总是将元素除队尾最后一个元素外,导入另一空队列中,最后一个元素出队。

本文链接:https://ariser.cn/index.php/archives/148/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!