代码随想录算法训练营第10天 | 栈和队列理论基础，232.用栈实现队列，225.用队列实现栈

栈和队列理论基础

栈是先进后出的数据结构，队列是先进先出的结构。如图所示。

C++中的STL有三儿比较普遍的版本：

• HP STL，是C++ STL的第一个实现版本，而且开放源代码。

• P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。

• SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

C++的栈和队列不是一个容器，而是一个容器适配器，其内部的数据存储形式可以由不同的其他数据实现，如vector, deque, list等。

目前使用最广泛的SGI STL中，deque是默认的栈的底层实现。开发者也可以指定栈的底层实现。

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

队列的情况一样，SGI STL中队列一样是以deque为默认情况下的底部结构。也可以手动指定：

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

232.用栈实现队列

代码随想录链接

题目

LeetCode-232

使用栈实现队列。又是在王道上做过的题

自己的想法

使用两个栈，A栈负责接收输入的数据，在遇到取队首或者出队操作时，若B栈为空，将A栈的元素依次弹出并压入B栈，此时B栈栈顶即为“队首”，若B栈不为空，直接操作B栈栈顶即可。

解法

class MyQueue {
private:
    stack<int> in, out;                 // 用于接收输入数据和输出数据的两个栈
public:
    MyQueue() {

    }
    
    void push(int x) {
        in.push(x);                     // 直接放入in栈中
    }
    
    int pop() {
        if (out.empty()) {              // 若输出栈out为空
            while (!in.empty()) {       // 将in栈中的所有元素弹出并压入out栈
                out.push(in.top());
                in.pop();
            }
        }
        if (!out.empty()) {             // 当out栈不为空时，取值并弹出元素
            int val = out.top();
            out.pop();
            return val;
        }
        return -1;
    }
    
    int peek() {
        int frontVal = this -> pop();     // 调用已经写好的pop函数来获得队首值
        out.push(frontVal);               // 将值放置到原位置上
        return frontVal;
    }
    
    bool empty() {
        return in.empty() && out.empty();
    }
};

225.用队列实现栈

代码随想录链接

题目

LeetCode-225

使用队列来实现栈。

自己的想法

重点在处理出栈操作。思路是将队列中的元素不断出队，直到原来在队尾（即“栈顶”）的元素到达队首，再对队首进行出队操作即可。

解法

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

    }
    
    void push(int x) {              // “压栈”操作，直接进队
        q.push(x);
    }
    
    int pop() {
        int size = q.size();        // 获得元素个数
        int tmp;
        while (--size) {            // 重复（队长 - 1）次
            tmp = q.front();        // 队首出队并重新入队
            q.pop();
            q.push(tmp);
        }
        int val = q.front();        // 取此时队首并返回
        q.pop();
        return val;
    }
    
    int top() {
        int topVal = this -> pop(); // 重复利用上面的函数，获得“栈顶”
        q.push(topVal);             // 将该元素重新入队，复原栈
        return topVal;
    }
    
    bool empty() {
        return q.empty();
    }
};