225-用队列实现栈

LeetCode 225. Implement Stack using Queues

LeetCode-225

Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.

method

往队里插入元素时，默认是在队尾插入的，所以要实现先入后出，就要先把之前的元素弹出再插入

class MyStack {
public:
    queue<int> q;
    MyStack() {}

    void push(int x) {
        int size = q.size();    // 记录当前队里的元素数量
        q.push(x);
        while (size--) {    // 前面的所有元素要先弹出再插入
            int tmp = q.front();
            q.pop();
            q.push(tmp);
        }
    }
    
    int pop() {
        int x = q.front();
        q.pop();
        return x;
    }

    int top() {
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
};