1
#include <deque>
2

3
template <typename T, typename Container = std::deque<T>>
4
class stack {
5
protected:
6
    Container c;  // 底层容器（默认为 std::deque）
7

8
public:
9
    // ========== 容量查询 ==========
10
    bool empty() const       { return c.empty(); }
11
    std::size_t size() const { return c.size(); }
12

13
    // ========== 栈顶访问 ==========
14
    T& top()                 { return c.back(); }
15
    const T& top() const     { return c.back(); }
16

17
    // ========== 压栈 ==========
18
    void push(const T& x)   { c.push_back(x); }
19
    void push(T&& x)        { c.push_back(std::move(x)); }
20

21
    template <typename... Args>
22
    void emplace(Args&&... args) {
23
        c.emplace_back(std::forward<Args>(args)...);
24
    }
25

26
    // ========== 出栈 ==========
27
    void pop()               { c.pop_back(); }
28

29
    // 注意：pop() 不返回被弹出的元素！
30
    // 原因：如果返回 T（按值），可能触发拷贝构造，
31
    //       如果拷贝构造抛异常，元素已经被移除了 → 数据丢失。
32
    //       分成 top() + pop() 两步操作是异常安全的设计。
33
};

1
template <typename T, std::size_t MaxDepth>
2
class FixedStack {
3
    static_assert(MaxDepth > 0, "MaxDepth must be > 0");
4

5
    std::array<T, MaxDepth> _data;
6
    int _top = -1;  // 指向当前栈顶，-1 表示空
7

8
public:
9
    bool push(const T& val) {
10
        if (_top >= static_cast<int>(MaxDepth) - 1) {
11
            return false;  // 栈满
12
        }
13
        _data[++_top] = val;
14
        return true;
15
    }
16

17
    template <typename... Args>
18
    bool emplace(Args&&... args) {
19
        if (_top >= static_cast<int>(MaxDepth) - 1) return false;
20
        _data[++_top] = T(std::forward<Args>(args)...);
21
        return true;
22
    }
23

24
    void pop() {
25
        if (_top >= 0) --_top;
26
    }
27

28
    T& top() { return _data[_top]; }
29
    const T& top() const { return _data[_top]; }
30

31
    bool empty() const { return _top == -1; }
32
    bool full() const { return _top == static_cast<int>(MaxDepth) - 1; }
33
    std::size_t size() const { return static_cast<std::size_t>(_top + 1); }
34
    std::size_t capacity() const { return MaxDepth; }
35
};

1
template <typename T>
2
class LinkedStack {
3
    struct Node {
4
        T data;
5
        Node* next;
6
        Node(const T& val, Node* n) : data(val), next(n) {}
7
    };
8

9
    Node* _top = nullptr;
10
    std::size_t _size = 0;
11

12
public:
13
    ~LinkedStack() { while (!empty()) pop(); }
14

15
    void push(const T& val) {
16
        _top = new Node(val, _top);  // 新节点指向旧栈顶
17
        ++_size;
18
    }
19

20
    void pop() {
21
        if (!_top) return;
22
        Node* old = _top;
23
        _top = _top->next;
24
        delete old;
25
        --_size;
26
    }
27

28
    T& top() { return _top->data; }
29
    const T& top() const { return _top->data; }
30

31
    bool empty() const { return _top == nullptr; }
32
    std::size_t size() const { return _size; }
33
};

1
class MinStack {
2
    std::stack<int> _data;
3
    std::stack<int> _min;  // 同步维护最小值
4

5
public:
6
    void push(int val) {
7
        _data.push(val);
8
        if (_min.empty() || val <= _min.top()) {
9
            _min.push(val);
10
        }
11
    }
12

13
    void pop() {
14
        if (_data.top() == _min.top()) {
15
            _min.pop();  // 弹出的恰好是当前最小值
16
        }
17
        _data.pop();
18
    }
19

20
    int top()    { return _data.top(); }
21
    int getMin() { return _min.top(); }
22
};
23
// 所有操作 O(1), 空间 O(n)

1
int evalRPN(std::vector<std::string>& tokens) {
2
    std::stack<int> st;
3

4
    for (const auto& token : tokens) {
5
        if (token == "+" || token == "-" ||
6
            token == "*" || token == "/") {
7
            // 遇到运算符：弹出两个操作数，计算后压回
8
            int b = st.top(); st.pop();  // 注意：b 是后弹出的（右操作数）
9
            int a = st.top(); st.pop();  // a 是先弹出的（左操作数）
10

11
            if      (token == "+") st.push(a + b);
12
            else if (token == "-") st.push(a - b);
13
            else if (token == "*") st.push(a * b);
14
            else if (token == "/") st.push(a / b);  // 题目保证不除 0
15
        } else {
16
            // 遇到数字：直接压栈
17
            st.push(std::stoi(token));
18
        }
19
    }
20
    return st.top();  // 栈中最后剩的就是结果
21
}
22
// 时间 O(n), 空间 O(n)

1
std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
2
    int n = temperatures.size();
3
    std::vector<int> result(n, 0);
4
    std::stack<int> st;  // 存下标，栈内下标对应的温度单调递减
5

6
    for (int i = 0; i < n; ++i) {
7
        // 当前温度 > 栈顶下标的温度 → 栈顶找到了它的答案
8
        while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
9
            int prev = st.top();
10
            st.pop();
11
            result[prev] = i - prev;  // 天数差
12
        }
13
        st.push(i);
14
    }
15
    // 栈中剩余的下标，右边没有更大的 → 结果保持 0
16
    return result;
17
}
18
// 时间 O(n)：每个元素最多进栈一次、出栈一次
19
// 空间 O(n)

1
Step 1: 暴力想法
2
  对每个柱子 i, 向左右扩展找到"以 heights[i] 为高的最大矩形"
3
  → 对每个 i, 找左边第一个比它矮的 L[i], 右边第一个比它矮的 R[i]
4
  → 面积 = heights[i] × (R[i] - L[i] - 1)
5
  → 暴力找 L[i] 和 R[i] 各 O(n) → 总 O(n²), 太慢
6

7
Step 2: 优化方向
8
  "找左/右边第一个更小的元素" ← 这就是单调栈的经典模型!
9

10
Step 3: 单调递增栈
11
  维护一个栈底到栈顶单调递增的栈 (存下标)
12
  当新柱子比栈顶矮时, 栈顶柱子找到了它的"右边界" (当前 i)
13
  弹出后, 新的栈顶就是它的"左边界"
14
  → 面积 = height[弹出] × (i - 新栈顶 - 1)
15

16
Step 4: 技巧
17
  在末尾追加高度为 0 的虚拟柱子 → 保证所有柱子都被弹出处理
18
  (否则循环结束后还要额外处理栈中剩余元素)

1
int largestRectangleArea(std::vector<int>& heights) {
2
    int n = heights.size();
3
    std::stack<int> st;  // 单调递增栈（存下标）
4
    int max_area = 0;
5

6
    for (int i = 0; i <= n; ++i) {
7
        // 在末尾加一个高度为 0 的虚拟柱子，保证所有柱子都会被弹出
8
        int cur_height = (i == n) ? 0 : heights[i];
9

10
        while (!st.empty() && cur_height < heights[st.top()]) {
11
            int h = heights[st.top()];  // 被弹出柱子的高度
12
            st.pop();
13

14
            // 宽度 = 左边界到右边界
15
            // 左边界：栈顶的下一个元素（如果栈空则为 -1）
16
            // 右边界：当前的 i（第一个比 h 矮的）
17
            int width = st.empty() ? i : (i - st.top() - 1);
18
            max_area = std::max(max_area, h * width);
19
        }
20
        st.push(i);
21
    }
22
    return max_area;
23
}
24
// 时间 O(n), 空间 O(n)

1
class MyQueue {
2
    std::stack<int> _in;   // 专管入队
3
    std::stack<int> _out;  // 专管出队
4

5
    // 惰性转移：只在 out 空时才倒
6
    void _transfer() {
7
        if (_out.empty()) {
8
            while (!_in.empty()) {
9
                _out.push(_in.top());
10
                _in.pop();
11
            }
12
        }
13
    }
14

15
public:
16
    void push(int x)  { _in.push(x); }
17

18
    int pop() {
19
        _transfer();
20
        int val = _out.top();
21
        _out.pop();
22
        return val;
23
    }
24

25
    int peek() {
26
        _transfer();
27
        return _out.top();
28
    }
29

30
    bool empty() { return _in.empty() && _out.empty(); }
31
};
32
// push: O(1)
33
// pop/peek: 均摊 O(1)（每个元素最多被倒一次）

1
Step 1: 直觉
2
  每个位置 i 能接的水 = min(左边最高, 右边最高) - height[i]
3
  (像一个桶, 水面高度由最矮的那边决定)
4

5
Step 2: 暴力 O(n²)
6
  对每个 i, 向左扫找 left_max, 向右扫找 right_max
7
  water[i] = min(left_max, right_max) - height[i]
8

9
Step 3: DP 预处理 O(n) 时间 / O(n) 空间
10
  预计算 left_max[i] 和 right_max[i] 数组 → 避免重复扫描
11

12
Step 4: 单调栈 O(n) / O(n)
13
  和 LC 84 同一模型: 维护单调递减栈
14
  遇到比栈顶高的柱子时, 可以"横向填水"
15
  → 弹出凹槽底部, 用左右墙高度算积水
16

17
Step 5: 双指针 O(n) / O(1) ← 最优
18
  关键洞察: 对于位置 i, 如果 left_max < right_max,
19
  那 water[i] = left_max - height[i] (右边一定够高, 不用管)
20
  → 双指针从两端往中间走, 总是移动较矮的一端

1
int trap(std::vector<int>& height) {
2
    std::stack<int> stk;  // 存下标，对应高度单调递减
3
    int water = 0;
4

5
    for (int i = 0; i < static_cast<int>(height.size()); ++i) {
6
        // 当前柱子比栈顶高 → 可以接水
7
        while (!stk.empty() && height[i] > height[stk.top()]) {
8
            int bottom = stk.top();  // 凹槽底部
9
            stk.pop();
10

11
            if (stk.empty()) break;  // 左边没有墙，接不住水
12

13
            int left = stk.top();    // 左墙
14
            int w = i - left - 1;    // 宽度
15
            int h = std::min(height[left], height[i]) - height[bottom];  // 高度
16
            water += w * h;
17
        }
18

19
        stk.push(i);
20
    }
21
    return water;
22
}
23
// 时间 O(n), 空间 O(n)

1
// 双指针解法（O(1) 空间）
2
int trap_two_pointers(std::vector<int>& height) {
3
    int left = 0, right = height.size() - 1;
4
    int left_max = 0, right_max = 0;
5
    int water = 0;
6

7
    while (left < right) {
8
        if (height[left] < height[right]) {
9
            left_max = std::max(left_max, height[left]);
10
            water += left_max - height[left];  // 被左右较矮的一侧限制
11
            ++left;
12
        } else {
13
            right_max = std::max(right_max, height[right]);
14
            water += right_max - height[right];
15
            --right;
16
        }
17
    }
18
    return water;
19
}
20
// 时间 O(n), 空间 O(1)

1
std::string decodeString(const std::string& s) {
2
    std::stack<int> num_stack;
3
    std::stack<std::string> str_stack;
4
    std::string current;
5
    int num = 0;
6

7
    for (char c : s) {
8
        if (std::isdigit(c)) {
9
            num = num * 10 + (c - '0');  // 处理多位数（如 "12[a]"）
10
        }
11
        else if (c == '[') {
12
            // 保存当前状态
13
            num_stack.push(num);
14
            str_stack.push(current);
15
            // 重置
16
            num = 0;
17
            current.clear();
18
        }
19
        else if (c == ']') {
20
            // 弹出重复次数和外层字符串
21
            int repeat = num_stack.top(); num_stack.pop();
22
            std::string outer = str_stack.top(); str_stack.pop();
23

24
            // 重复 current，拼到 outer 后面
25
            for (int i = 0; i < repeat; ++i) {
26
                outer += current;
27
            }
28
            current = std::move(outer);
29
        }
30
        else {
31
            current += c;  // 普通字符直接累积
32
        }
33
    }
34
    return current;
35
}

1
c='3': num=3
2
c='[': push(3, ""), num=0, current=""
3
         num_stack: [3]  str_stack: [""]
4

5
c='a': current="a"
6

7
c='2': num=2
8
c='[': push(2, "a"), num=0, current=""
9
         num_stack: [3,2]  str_stack: ["","a"]
10

11
c='c': current="c"
12

13
c=']': pop(2, "a") → outer = "a" + "c"×2 = "acc"
14
         current = "acc"
15
         num_stack: [3]  str_stack: [""]
16

17
c=']': pop(3, "") → outer = "" + "acc"×3 = "accaccacc"
18
         current = "accaccacc"
19

20
结果: "accaccacc" ✅

1
// UI 面板的生命周期接口
2
class UIPanel {
3
public:
4
    virtual ~UIPanel() = default;
5
    virtual void OnEnter()  = 0;  // 首次进入（播放进场动画）
6
    virtual void OnExit()   = 0;  // 被关闭（播放退场动画，释放资源）
7
    virtual void OnPause()  = 0;  // 被新面板覆盖（失去焦点，停止接收输入）
8
    virtual void OnResume() = 0;  // 上层面板关闭，重新获得焦点
9
    virtual void OnUpdate(float dt) = 0;
10
    virtual void OnRender() = 0;
11
};
12

13
class UIManager {
14
    std::stack<std::unique_ptr<UIPanel>> _stack;
15

16
public:
17
    // 打开新面板 —— Push
18
    void OpenPanel(std::unique_ptr<UIPanel> panel) {
19
        if (!_stack.empty()) {
20
            _stack.top()->OnPause();   // 当前面板失焦
21
        }
22
        panel->OnEnter();              // 新面板入场
23
        _stack.push(std::move(panel));
24
    }
25

26
    // 关闭当前面板 —— Pop
27
    void CloseCurrentPanel() {
28
        if (_stack.empty()) return;
29

30
        _stack.top()->OnExit();        // 当前面板退场
31
        _stack.pop();                  // 销毁
32

33
        if (!_stack.empty()) {
34
            _stack.top()->OnResume();  // 下层面板恢复焦点
35
        }
36
    }
37

38
    // 关闭所有面板（回到主界面）
39
    void CloseAll() {
40
        while (!_stack.empty()) {
41
            _stack.top()->OnExit();
42
            _stack.pop();
43
        }
44
    }
45

46
    // 只更新/渲染栈顶面板（或者根据需求渲染多层）
47
    void Update(float dt) {
48
        if (!_stack.empty()) {
49
            _stack.top()->OnUpdate(dt);
50
        }
51
    }
52

53
    void Render() {
54
        // 可以选择渲染所有层（半透明叠加效果）
55
        // 简化版：只渲染栈顶
56
        if (!_stack.empty()) {
57
            _stack.top()->OnRender();
58
        }
59
    }
60

61
    bool HasPanel() const { return !_stack.empty(); }
62
    std::size_t Depth() const { return _stack.size(); }
63
};

1
class GameState {
2
public:
3
    virtual ~GameState() = default;
4
    virtual void OnEnter()  = 0;
5
    virtual void OnExit()   = 0;
6
    virtual void OnPause()  = 0;
7
    virtual void OnResume() = 0;
8
    virtual void Update(float dt) = 0;
9
    virtual void Render() = 0;
10
};
11

12
class GameStateManager {
13
    std::stack<std::unique_ptr<GameState>> _states;
14

15
public:
16
    // 压入新状态（不销毁旧状态）
17
    void PushState(std::unique_ptr<GameState> state) {
18
        if (!_states.empty()) {
19
            _states.top()->OnPause();
20
        }
21
        state->OnEnter();
22
        _states.push(std::move(state));
23
    }
24

25
    // 弹出当前状态（恢复下层状态）
26
    void PopState() {
27
        if (_states.empty()) return;
28
        _states.top()->OnExit();
29
        _states.pop();
30
        if (!_states.empty()) {
31
            _states.top()->OnResume();
32
        }
33
    }
34

35
    // 替换当前状态（弹出旧的 + 压入新的）
36
    void ChangeState(std::unique_ptr<GameState> state) {
37
        if (!_states.empty()) {
38
            _states.top()->OnExit();
39
            _states.pop();
40
        }
41
        state->OnEnter();
42
        _states.push(std::move(state));
43
    }
44

45
    void Update(float dt) {
46
        if (!_states.empty()) {
47
            _states.top()->Update(dt);
48
        }
49
    }
50

51
    // 渲染可以从底部往上全部渲染（实现半透明叠加）
52
    void Render() {
53
        // 简化：用临时容器逆序渲染
54
        // 完整实现可以用 vector<GameState*> 替代 stack 来支持底层遍历
55
        if (!_states.empty()) {
56
            _states.top()->Render();
57
        }
58
    }
59
};

1
// 命令接口 —— 每个可撤销的操作都是一个 Command
2
class Command {
3
public:
4
    virtual ~Command() = default;
5
    virtual void Execute() = 0;   // 执行
6
    virtual void Undo() = 0;      // 撤销（执行逆操作）
7
    virtual std::string Description() const = 0;
8
};
9

10
// ===== 具体命令示例：移动实体 =====
11
class MoveEntityCommand : public Command {
12
    Entity* _entity;
13
    Vec2 _old_pos;
14
    Vec2 _new_pos;
15

16
public:
17
    MoveEntityCommand(Entity* e, Vec2 new_pos)
18
        : _entity(e), _old_pos(e->position), _new_pos(new_pos) {}
19

20
    void Execute() override { _entity->position = _new_pos; }
21
    void Undo() override    { _entity->position = _old_pos; }
22
    std::string Description() const override {
23
        return "Move " + _entity->name;
24
    }
25
};
26

27
// ===== Undo/Redo 管理器 =====
28
class UndoRedoManager {
29
    std::stack<std::unique_ptr<Command>> _undo_stack;
30
    std::stack<std::unique_ptr<Command>> _redo_stack;
31

32
public:
33
    void Execute(std::unique_ptr<Command> cmd) {
34
        cmd->Execute();
35
        _undo_stack.push(std::move(cmd));
36

37
        // 关键：执行新操作后，redo 历史作废
38
        while (!_redo_stack.empty()) _redo_stack.pop();
39
    }
40

41
    void Undo() {
42
        if (_undo_stack.empty()) return;
43

44
        auto cmd = std::move(_undo_stack.top());
45
        _undo_stack.pop();
46
        cmd->Undo();
47
        _redo_stack.push(std::move(cmd));
48
    }
49

50
    void Redo() {
51
        if (_redo_stack.empty()) return;
52

53
        auto cmd = std::move(_redo_stack.top());
54
        _redo_stack.pop();
55
        cmd->Execute();
56
        _undo_stack.push(std::move(cmd));
57
    }
58

59
    bool CanUndo() const { return !_undo_stack.empty(); }
60
    bool CanRedo() const { return !_redo_stack.empty(); }
61
};