代码随想录算法训练营第10天 | 栈和队列

理论基础

• 栈和队列是STL（C++标准库）里面的两个数据结构
• STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）
• 栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现
  
• 我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构
  • deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了
  • SGI STL中 队列底层实现缺省情况下一样使用deque实现的
  • 我们也可以指定vector为栈的底层实现，初始化语句如下
    std::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列
• 栈和队列不允许遍历，不提供迭代器

232.用栈实现队列

stack用法
一个栈输入，一个栈输出

class MyQueue {
public:
    MyQueue() {

    }

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

    int pop() {
        if(stOut.empty()) {
            while (!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }

        int result = stOut.top();
        stOut.pop();  //此pop()不返回值
        return result;
    }

    int peek() {
        if (stOut.empty()) {
            while (!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }

        return stOut.top();

        //int res = this->pop(); // 直接使用已有的pop函数
        //stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
        //return res;
    }

    bool empty() {
        if (stOut.empty() && stIn.empty())
            return true;
        else
            return false;
    }

private:
    stack<int> stIn;
    stack<int> stOut;

};

225. 用队列实现栈

queue用法

• 两个队列：其中一个队列用来暂时存放
  

class MyStack {
public:
    queue<int> que1;
    queue<int> que2; // 辅助队列，用来备份
    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        que1.push(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que1.size();
        size--;
        while (size--) { // 将que1 导入que2，但要留下最后一个元素
            que2.push(que1.front());
            que1.pop();
        }

        int result = que1.front(); // 留下的最后一个元素就是要返回的值
        que1.pop();
        que1 = que2;            // 再将que2赋值给que1
        while (!que2.empty()) { // 清空que2
            que2.pop();
        }
        return result;
    }

    /** Get the top element. */
    int top() {
        return que1.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que1.empty();
    }
};

• 一个队列实现

class MyStack {
public:
    MyStack() {

    }

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

    int pop() {
        int size = stack.size();
        while (--size) {
            stack.push(stack.front());
            stack.pop();
        }
        int result = stack.front();
        stack.pop();
        return result;
    }

    int top() {
        return stack.back();
    }

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

private:
    queue<int> stack;
};