栈与队列理论基础

栈与队列的异同
相同点：
1.都是一种线性结构
2.插入操作都限定在表尾进行
3.都可以通过顺序结构和链式结构实现

4. 插入和删除的时间复杂度都是O(1)，在空间上也一样
5. 多链栈和多链队列的管理模式可以相同

不同点：
1.删除数据元素的位置不同，栈的删除操作在表尾进行，队列的删除操作在表头进行
2.应用场景不同；常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等；常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等
3.顺序栈能够实现多栈空间共享，而顺序队列不能

232.用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

题目：使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。

分析：这是一道模拟题，不涉及具体的算法，用栈来实现队列的操作，就不能使用一个栈，至少要用两个栈来实现队列的操作，一个输入栈，一个输出栈。

在输入栈中，只要把数据输入进去就可以了，但是在输出栈中，如果输出栈为空，就要把输入栈的数据全部导入进行，如果输入栈不为空，就直接输出数据就好了。

如果输入栈和输出栈都为空的话，那么就可以判断队列为空了

c++中stack的常用方法：
(1). push(x) 将x入栈

(2). top() 获得栈顶元素

(3). pop() 用以弹出栈顶元素

(4). empty() 可以检测stack内是否为空，返回true为空，返回false为非空

(5). size() 返回stack内元素的个数

class MyQueue {
public:
    stack<int> stackIn;
    stack<int> stackOut;
    MyQueue() {

    }
    
    void push(int x) {
        stackIn.push(x);
    }
    
    int pop() {//对输出栈进行判断，若为空，把输入栈的值全部放进输出栈中输出1
        if(stackOut.empty()){
            while(!stackIn.empty()){
                stackOut.push(stackIn.top());
                stackIn.pop();
            }
        }
        int result = stackOut.top();//不为空，直接输出
        stackOut.pop();
        return result;
    }
    
    int peek() {
        int res = this->pop();
        stackOut.push(res);
        return res;
    }
    
    bool empty() {
        return stackIn.empty() && stackOut.empty();//当输出栈和输出栈都为空时，队列为空
    }
};

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

255.用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）
题目：
使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

思路：使用两个队列来实现栈的模拟，其中一个栈用来备份

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();
    }
};