第10天-代码随想录刷题训练-第五章栈和队列- ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈-Toy模板网

这篇具有很好参考价值的文章主要介绍了第10天-代码随想录刷题训练-第五章栈和队列- ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 理论基础

栈和队列对应的三个不同的STL版本，底层实现方式不一样, 为我们所知道的是 SGI STL

栈

栈提供 pop和push等接口，不提供走访功能
也不提供迭代器，不像map和set可以使用迭代器遍历，往往不被归类为容器，而是容器适配器
栈的内部实现结构可以使用 verctor、list 和 deque(默认)
可以在初始化的时候指定使用哪种底层实现

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

第10天-代码随想录刷题训练-第五章栈和队列- ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈
栈的api
stack 包含在头文件中
成员函数
- top() 返回头部元素
- empty() 检查是否为空 size() 返回容纳的元素
- push() 顶层插入元素， emplace() 在顶层构造元素 pop() 返回为void，直接删除元素 swap()

2. 用两个栈实现队列

LeetCode 链接

注意点
- pop返回的是void，要弹出并获取顶部的值应该先top再pop
- 两个栈有一个不为空就返回false，因此是 is.empty() && os.empty()
  实现思路图：

class MyQueue {
public:
    MyQueue() {
    }

    stack<int> is;
    stack<int> os;
    
    void push(int x) {
        // 将数据直接压入is 栈
        is.push(x);
    }
    
    int pop() {
        // 得先判断os中是否还有元素，如果有直接弹出，否则从is中弹出压入到os
        // 先将is栈中的内容 逐个弹出 压入 os栈，知道所有is中都空则弹出os栈的第一个元素
        if(os.empty()){
            while(!(is.empty())){
                os.push(is.top());
                is.pop();
            }
        }
        int top = os.top();
        os.pop();
        return top;     
    }
    
    int peek() {
        if(os.empty()){
            while(!(is.empty())){
                os.push(is.top());
                is.pop();
            }
        }
        return os.top();
    }
    
    bool empty() {
        return os.empty() && is.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();
 */

3. 两个队列实现栈

LeetCode
queue api
第10天-代码随想录刷题训练-第五章栈和队列- ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈

class MyStack {
public:
    MyStack() {

    }
    queue<int> qi;
    queue<int> qo;

    void push(int x) {
        qi.push(x);
    }
    
    int pop() {
        int size = qi.size();
        while(--size){
            qo.push(qi.front());
            qi.pop();
        }
        int result = qi.front();
        qi.pop();

        while(!qo.empty()){
            qi.push(qo.front());
            qo.pop();
        }

        return result;
    }
    
    int top() {
        return qi.back();
    }
    
    bool empty() {
        return qi.empty() && qo.empty();
    }
};

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

优化，每次弹出的时候只需要将弹出的元素重新添加到队尾文章来源地址https://www.toymoban.com/news/detail-444573.html

class MyStack {
public:
    MyStack() {

    }
    queue<int> qi;

    void push(int x) {
        qi.push(x);
    }
    
    int pop() {
        int size = qi.size();
        while(--size){
            qi.push(qi.front());
            qi.pop();
        }
        int result = qi.front();
        qi.pop();
        return result;
    }
    
    int top() {
        return qi.back();
    }
    
    bool empty() {
        return qi.empty();
    }
};

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