栈与队列

栈：先进后出 （叠起来的盘子 Stack）
队列：先进先出 （现实中排队 Queue）

三个版本的STL

1. HP STL，其他STL的蓝本，开源
2. P.J.Plauger STL， 被Visual C++采用，不开源
3. SGI STL，被Linux中GCC所采用，开源

底层实现

栈与队列的底层容器时可插拔的（可以更换），STL中他们不被归类为容器，而是container adapter（容器适配器）。

对于SGI STL，在底层缺失的情况下，默认使用deque（双向队列）来实现。

例子

std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈

std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

栈与队列 lc232 用栈实现队列

使用两个栈实现队列的操作。pop前需要检查出栈是否为空。

class MyQueue {
public:
    MyQueue() {

    }
    
    void push(int x) {
        instack.push(x);
    }
    
    int pop() {
        if (outstack.empty()){
            while(!instack.empty()){
                outstack.push(instack.top());
                instack.pop();
            }
        }
        int result = outstack.top();
        outstack.pop();
        return result;
    }
    
    int peek() {
        int result = this->pop();
        outstack.push(result);
        return result;
    }
    
    bool empty() {
        return(instack.empty() && outstack.empty());
    }
private:
    stack<int> instack,outstack;
};

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

栈与队列 lc225 用队列实现栈

队列实现栈只需要一个队列就可以。获取到队列的大小后，将除了队列最后的一个元素外，其他元素循环从头部弹出队列再从尾部进入队列，此时再弹出最后一个元素即可。同时队列中的尾部queue.back() 其实就相当于栈中的头部stack.top()，即最近一次加入的元素。

class MyStack {
public:
    MyStack() {

    }
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int n_move = que.size()-1;
        while(n_move--){
            que.push(que.front());
            que.pop();
        }
        int result = que.front();
        que.pop();
        return result;
    }
    
    int top() {
        return que.back();
    }
    
    bool empty() {
        return que.empty();
    }
private:
    queue<int> que;
};

/**
 * 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();
 */