栈

用栈实现队列

用栈实现队列

class MyQueue {
private:stack<int> st_in;  // 输入栈，用于压入传入的数据stack<int> st_out; // 输出栈，st_out为st_in的倒序
public:MyQueue() {}void push(int x) {st_in.push(x);}int pop() {  if (st_out.empty()) {while (!st_in.empty()) {st_out.push(st_in.top()); st_in.pop();}}int out = st_out.top();st_out.pop();return out;}int peek() {int out = this->pop();st_out.push(out);return out;}bool empty() { return st_in.empty() && st_out.empty(); }
};

最小栈 (Hot 100)

最小栈

class MinStack {
private:stack<int>x_stack;stack<int>min_stack; // size与x_stack相同，存储当前最小值
public:MinStack() {min_stack.push(INT_MAX);}void push(int val) {x_stack.push(val);min_stack.push(min(min_stack.top(),val));}void pop() {x_stack.pop();min_stack.pop();}int top() {return x_stack.top();}int getMin() {return min_stack.top();}
};

有效的括号 (Hot 100)

有效的括号

class Solution {
public:bool isValid(string s) {if (s.size() % 2 != 0) return false;stack<char> st;for (int i = 0; i < s.size(); i++){if (s[i] == '(') st.push(')');else if (s[i] == '[')  st.push(']');else if (s[i] == '{') st.push('}');// 不匹配或者还没遍历完，栈为空// 注意，不能是(s[i] != st.top() ||st.empty()),因为空栈没有.top()else if (st.empty()||st.top() != s[i]) return false;else st.pop();}return st.empty();  // 栈为空，则有效}
};

字符串解码 (Hot 100)

字符串解码

class Solution {
public:string decodeString(string s) {stack<pair<string, int>> matchStack;string cur_str;int multi = 0;for (char& ch : s) {if (ch == '[') {matchStack.push({cur_str, multi});multi = 0;cur_str.clear();} else if (ch == ']') {auto [pre_str, cnt] = matchStack.top();matchStack.pop();  // pre_str是上个 [ 到当前 [ 的字符串，例如 "3[a2[c]]" 中的 a；for (int i = 0; i < cnt; i++)pre_str += cur_str; cur_str = pre_str;} else if (ch >= '0' and ch <= '9') {multi = multi * 10 + (int)(ch - '0');} elsecur_str += ch;}return cur_str;}
};

每日温度 (Hot 100)

每日温度

class Solution {  
public:  vector<int> dailyTemperatures(vector<int>& T) {  // 递增栈：存储温度序列中元素的索引，保证栈顶索引对应的温度从栈顶到栈底是递增的  stack<int> st;  // 结果数组，用于存储每天需要等待的天数，初始化为0  vector<int> result(T.size(), 0);  // 将第一个温度的索引压入栈中  st.push(0);  // 从第二个温度开始遍历温度序列  for (int i = 1; i < T.size(); i++) {  // 情况一：如果当前温度小于等于栈顶索引对应的温度  // 则将当前温度的索引压入栈中，因为栈中需要保持递增的温度  if (T[i] <= T[st.top()]) st.push(i);                          // 情况二：如果当前温度大于s栈顶索引对应的温度  // 则弹出栈顶索引，直到找到一个比当前温度更低的温度，或者栈为空  else {  while (!st.empty() && T[i] > T[st.top()]) {   // 更新栈顶索引需要等待的天数，为当前索引减去栈顶索引result[st.top()] = i - st.top();  st.pop();  }  st.push(i);  }  }  return result;  }  
};

简化：

class Solution {
public:vector<int> dailyTemperatures(vector<int>& T) {stack<int> st; // 递增栈vector<int> result(T.size(), 0);for (int i = 0; i < T.size(); i++) {while (!st.empty() && T[i] > T[st.top()]) { result[st.top()] = i - st.top();st.pop();}st.push(i);}return result;}
};