栈与队列理论基础

deque为缺省指定底层实现的stack和queue的默认底层结构。
STL中栈和队列不被归为容器，而被归为容器适配器。
栈先进后出，队列先进先出。

刷题笔记day10

232.用栈实现队列

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

创建两个stack，相当于倒序排列来获取头部元素。

自己写的代码

class MyQueue {
public:
    stack<int> stin;
    stack<int> stout;

    MyQueue() {

    }
    
    void push(int x) {
        stin.push(x);
    }
    
    int pop() {
        if (stout.empty()) {
            while (!stin.empty()) {
                int out = stin.top();
                stin.pop();
                stout.push(out);
            }
        }
        int result = stout.top();
        stout.pop();
        return result;
    }
    
    int peek() {
        int result = this->pop();
        stout.push(result);
        return result;
    }
    
    bool empty() {
        if (stin.empty() && stout.empty()) {
            return true;
        }
        else {
            return false;
        }
    }
};

看了题解后的收获

两个stack都为空则empty()为true。
每次要提取或删除头元素的时候判断stout是否为空，空则将stin的元素全部倒序移入，非空则直接从stout中提取或删除元素。

225.用队列实现栈

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

用队列删除队尾元素的机制。

自己写的代码

看了题解后写的代码：

class MyStack {
public:
    queue<int> quein;
    queue<int> queout;

    MyStack() {

    }
    
    void push(int x) {
        quein.push(x);
    }
    
    int pop() {
        int size = quein.size();
        --size;
        while (size--) {
            queout.push(quein.front());
            quein.pop();
        }
        int result = quein.front();
        quein.pop();
        size = queout.size();
        while (size--) {
            quein.push(queout.front());
            queout.pop();
        }
        return result;
    }
    
    int top() {
        int result = this->pop();
        quein.push(result);
        return result;
    }
    
    bool empty() {
        return quein.empty();
    }
};

看了题解后的收获

善用queue的机制，掌握用单queue实现stack的解法。