剑指 Offer Day1——栈与队列（简单）

本专栏将记录《剑指 Offer》的刷题，传送门：https://leetcode.cn/study-plan/lcof/。

剑指 Offer 09. 用两个栈实现队列

原题链接：09. 用两个栈实现队列

class CQueue {
public:stack<int> s1, s2;  // s1为主栈，s2为辅助栈CQueue() {}void appendTail(int value) {s1.push(value);}int deleteHead() {if (s1.empty()) return -1;else {copy(s1, s2);int t = s2.top();s2.pop();copy(s2, s1);return t;}}// 将x的所有元素压入yvoid copy(stack<int> &x, stack<int> &y) {while (!x.empty()) {y.push(x.top());x.pop();}}
};

剑指 Offer 30. 包含min函数的栈

原题链接：30. 包含min函数的栈

同样设置两个栈，s1 为主栈用来存储数据，s2 为最小栈用来存储最小值。

class MinStack {
public:stack<int> s1, s2;  // s1是主栈，s2是最小栈MinStack() {s2.push(INT_MAX);}void push(int x) {s1.push(x);s2.push(std::min(x, s2.top()));}void pop() {s1.pop();s2.pop();}int top() {return s1.top();}int min() {return s2.top();}
};

一个直观的例子：

$$\begin{array}{rl}{s}_1:[& 3,5,6,1,4,0,2,7]\\ s_2:[\text{INT\_MAX},& 3,3,3,1,1,0,0,0]\end{array}$$

列表左端为栈底，右端为栈顶。