leetcode

题目描述

使用队列实现栈的下列操作：

• push(x) -- 元素 x 入栈
• pop() -- 移除栈顶元素
• top() -- 获取栈顶元素
• empty() -- 返回栈是否为空

解题思路

1. 可以使用两个队列
2. 也可以使用一个队列，我们在此只讲述双队列
   • 当使用队列实现栈时，另一个队列发挥着临时存储的作用
   • 队列先进先出和栈先进后出的特性要理解

最终代码

class MyStack {
public:
    queue<int> queueOne;
    queue<int> queueTwo;

    MyStack() {

    }
    
    void push(int x) {
        queueOne.push(x);
    }
    
    int pop() {
        int size = queueOne.size();
        // 为了在queueOne中留下一个
        size--;

        while (size--) {
            // 将queueOne的数据全部临时存储到queueTwo中
            queueTwo.push(queueOne.front());
            queueOne.pop();
        }
        // 返回结果
        int result = queueOne.front();
        queueOne.pop();
        // 将queueTwo赋值给queueOne
        queueOne = queueTwo;
        // 清空queueTwo
        while (!queueTwo.empty()) {
            queueTwo.pop();
        }
        return result;
    }
    
    int top() {
        return queueOne.back();
    }
    
    bool empty() {
        return queueOne.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */