剑指offer 09. 用两个栈实现队列 (easy)

#pragma once
#include<stack>

using std::stack;

// 使用辅助栈
class CQueue {
private:
    stack<int> in;         // 入队列的值 都push到栈in中(in栈顶元素正好是 队列中最后一个元素,in出栈顺序与出队正好相反)
    stack<int> out;        // 将栈in中的值出栈 并同时push到栈out中(根据栈的特性可知,此时栈out中的元素顺序 与之前栈in中的元素顺序正好相反。因此,此时out出栈顺序与出队正好相同)

public:
    CQueue() {             // 构造函数为默认构造函数即可

    }

    void appendTail(int value) {               // 入队的值都push到 栈in中
        in.push(value);
    }

    int deleteHead() {                         // 出队要借助 栈out
        if (out.empty()) {                     // 如果栈out为空,就需要将栈in中的值 都逆序导入到栈out中(经过这个if语句的操作后,栈in为空,原本栈in中的值 都逆序导入栈out中)
            while (!in.empty()) {              
                int top = in.top();
                out.push(top); 
                in.pop();                      
            }
        }
        
        if (out.empty()) {                     // 还需要检查一下栈out是否为空,如果不为空才能出栈(也就是出队)(避免原本栈in、栈out都为空的情况)
            return -1;
        }

        int front = out.top();                 // 保存要出队的值(就算栈out要出栈的值),待弹出栈顶之后 返回该值
        out.pop();
        return front;                          
    }
};

剑指offer 30. 包含min函数的栈 (easy)


#pragma once
#include<stack>

using std::stack;

// 使用辅助栈
class MinStack {
private:
    stack<int> stk_data;        // 数据栈stk_data
    stack<int> stk_min;         // 辅助栈stk_min (辅助栈stk_min中每个元素值 为数据栈stk_data中 从该对应位置到栈顶范围内 的所有元素 的最小值)

public:
    MinStack() {                // 默认构造函数即可

    }

    void push(int x) {
        stk_data.push(x);                               // 将x push到数据栈stk_data中
        if (stk_min.empty() || x < stk_min.top()) {     // 当 "辅助栈stk_min为空" 或者 "辅助栈顶stk_min不为空 但x小于辅助栈栈顶元素" 时,此时x为数据栈内的最小元素,则将x push到辅助栈中
            stk_min.push(x);
        }
        else {                                          // 否则表示x>=stk_min.top(),则push当前辅助栈栈顶元素 到辅助栈中 (表示当前数据栈中的最小值,还是原来的最小值)
            stk_min.push(stk_min.top());
        }
    }

    void pop() {
        if (!stk_data.empty()) {
            stk_data.pop();
            stk_min.pop();
        }
    }

    int top() {
        if (!stk_data.empty()) {
            return stk_data.top();
        }
        return INT_MIN;
    }

    int min() {
        if (!stk_data.empty()) {
            return stk_min.top();
        }

        return INT_MIN;
    }
};
优质题解:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/