栈实现队列

1. 思路

栈是一种存放元素有后进先出特性的数据结构。利用栈后进先出的特性，那么用两个栈，就可以把出栈的元素顺序变成我们入栈的元素顺序。

这样就可以用两个栈来翻转模拟队列先进先出。但是还有一个问题，这例子是一次性全部入栈，一次性全部出栈。如果是入栈-出栈-入栈这种操作要怎么处理。

前面已经知道了可以把一个栈的数据放到另一个栈中翻转来模拟队列的先进先出。出栈的那个栈肯定是不能放我们刚入队的数据的，这样会破坏元素的顺序。所有我们要一个栈用于模拟入队操作，另一个栈模拟出队操作。出队的栈一但空了，就去入队栈拿数据，这样就可以实现队列了。

2. 代码

class MyQueue {
public:
    stack<int> s1, s2;
    // s1 push
    // s2 pop
    
    MyQueue() {
    }
    
    void push(int x) {
        s1.push(x);
    }
    
    int pop() {
        int top;
        if (!s2.empty()) {
            top = s2.top();
            s2.pop();
        } else {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
            top = s2.top();
            s2.pop();
        }
        return top;
    }
    
    int peek() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }
    
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

队列实现栈

1. 思路

首先想到的是双端队列，可以很容易的实现栈操作。这个太简单了，用单向队列实现看看。

单向队列的特点是先进的元素先出，只能在一端入队，另一端出队。用一个队列肯定不行，用两个元素顺序也不会变，这咋整？？？

机智的你肯定想到办法了。在这队列里，出栈的元素肯定是最后一个元素。那么可以把队列挪到另一个队列中去，然后只留一个元素在原来队列，这样这个元素就是出栈的第一个元素了。每次出栈都要挪一次队列。

这样代码就很容易了。

2. 代码

class MyStack {
public:
    queue<int> q1, q2;
    
    MyStack() {
    }
    
    void push(int x) {
        // 哪个队列有元素就往哪个放
        if (!q1.empty()) {
            q1.push(x);
        } else if (!q2.empty()) {
            q2.push(x);
        } else {
            q1.push(x);
        }
    }
    
    int pop() {
        int p;
        if (!q1.empty()) { // 放元素的队列
            while (q1.size() != 1) {
                q2.push(q1.front());
                q1.pop();
            }
            // 剩下一个元素
            p = q1.front();
            q1.pop();
        } else {
            while (q2.size() != 1) {
                q1.push(q2.front());
                q2.pop();
            }
            p =  q2.front();
            q2.pop();
        }
        return p;
    }
    
    int top() {
        if (!q1.empty()) return q1.back();
        else return q2.back();
    }
    
    bool empty() {
        return q1.empty() && q2.empty();
    }
};