31天刷完剑指offer——(第1天) 栈和队列
剑指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/
31天刷完剑指offer 文章被收录于专栏
数据结构与算法