31天刷完剑指offer——(第1天) 栈和队列

#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;
    }
};