咋又要用队列实现栈了嘛？！


 

push(x)，入栈操作，先压入辅助队列，再将主队列的元素加入辅助队列，再互换主队列和辅助队列。

pop()，出栈操作，出栈出的是栈顶元素，由上图可以看出，栈顶元素即主队列的队首元素。

1. push() 在队尾插入一个元素
2. pop() 删除队列第一个元素
3. size() 返回队列中元素个数
4. empty() 如果队列空则返回true
5. front() 返回队列中的第一个元素
6. back() 返回队列中最后一个元素

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;

    MyStack() {
        
    }
    
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        int size = q1.size();
        size --;
        while(size--){
            q2.push(q1.front());
            q1.pop();
        }
        int reslut = q1.front();
        q1.pop();
        q1 = q2;
        while(!q2.empty()){
            q2.pop();
        }

        return reslut;
    }
    
    int top() {
        int size = q1.size();
        size--;
        while(size--){
            q2.push(q1.front());
            q1.pop();
        }
        int result = q1.front();
        q2.push(q1.front());
        q1.pop();
        q1 = q2;
        while(!q2.empty()){
            q2.pop();
        }
        return result;
    }
    
    bool empty() {
        return q1.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();
 */

用一个队列实现

class MyStack {
public:
    queue<int> que;

    MyStack() {

    }

    void push(int x) {
        que.push(x);
    }

    int pop() {
        int size = que.size();
        size--;
        while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
        que.pop();
        return result;
    }

    int top(){
        int size = que.size();
        size--;
        while (size--){
            // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result = que.front(); // 此时获得的元素就是栈顶的元素了
        que.push(que.front());    // 将获取完的元素也重新添加到队列尾部，保证数据结构没有变化
        que.pop();
        return result;
    }

    bool empty() {
        return que.empty();
    }
};