1
#include <deque>
2

3
template <typename T, typename Container = std::deque<T>>
4
class queue {
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& front()             { return c.front(); }
15
    const T& front() const { return c.front(); }
16
    T& back()              { return c.back(); }
17
    const T& back() const  { return c.back(); }
18

19
    // ========== 入队（尾部）==========
20
    void push(const T& x)   { c.push_back(x); }
21
    void push(T&& x)        { c.push_back(std::move(x)); }
22

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

28
    // ========== 出队（头部）==========
29
    void pop()               { c.pop_front(); }
30
    // 同 std::stack，pop() 不返回值——异常安全设计
31
};

1
template <
2
    typename T,
3
    typename Container = std::vector<T>,
4
    typename Compare = std::less<T>       // 默认最大堆
5
>
6
class priority_queue {
7
protected:
8
    Container c;
9
    Compare   comp;
10

11
public:
12
    // ========== 容量 ==========
13
    bool empty() const       { return c.empty(); }
14
    std::size_t size() const { return c.size(); }
15

16
    // ========== 堆顶（最大/最小元素）==========
17
    const T& top() const { return c.front(); }
18

19
    // ========== 入队（插入 + 上浮）==========
20
    void push(const T& x) {
21
        c.push_back(x);                    // 1. 先放到末尾
22
        std::push_heap(c.begin(), c.end(), comp);  // 2. sift-up 恢复堆序
23
    }
24

25
    // ========== 出队（堆顶移除 + 下沉）==========
26
    void pop() {
27
        std::pop_heap(c.begin(), c.end(), comp);  // 1. 堆顶换到末尾
28
        c.pop_back();                              // 2. 删除末尾
29
        // pop_heap 内部做了 sift-down 恢复堆序
30
    }
31
};

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

5
    // 多分配一个位置，用于区分"空"和"满"
6
    std::array<T, Capacity + 1> _buf{};
7
    std::size_t _front = 0;  // 队头（下一个出队的位置）
8
    std::size_t _rear  = 0;  // 队尾（下一个入队的位置）
9

10
    static constexpr std::size_t N = Capacity + 1;
11

12
    std::size_t _next(std::size_t idx) const {
13
        return (idx + 1) % N;
14
    }
15

16
public:
17
    bool enqueue(const T& value) {
18
        if (full()) return false;
19
        _buf[_rear] = value;
20
        _rear = _next(_rear);
21
        return true;
22
    }
23

24
    bool dequeue() {
25
        if (empty()) return false;
26
        _front = _next(_front);
27
        return true;
28
    }
29

30
    T& front() { return _buf[_front]; }
31
    const T& front() const { return _buf[_front]; }
32

33
    T& back() {
34
        // rear 的前一个位置就是最后入队的元素
35
        return _buf[(_rear + N - 1) % N];
36
    }
37

38
    bool empty() const { return _front == _rear; }
39
    bool full() const  { return _next(_rear) == _front; }
40

41
    std::size_t size() const {
42
        return (_rear + N - _front) % N;
43
    }
44

45
    std::size_t capacity() const { return Capacity; }
46
};

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

5
    std::array<T, Capacity + 1> _buf{};
6
    std::size_t _front = 0;
7
    std::size_t _rear  = 0;
8

9
    static constexpr std::size_t N = Capacity + 1;
10

11
    std::size_t _next(std::size_t idx) const { return (idx + 1) % N; }
12
    std::size_t _prev(std::size_t idx) const { return (idx + N - 1) % N; }
13

14
public:
15
    // ========== 尾部操作（和普通队列一样）==========
16
    bool insertLast(const T& value) {
17
        if (full()) return false;
18
        _buf[_rear] = value;
19
        _rear = _next(_rear);
20
        return true;
21
    }
22

23
    bool deleteLast() {
24
        if (empty()) return false;
25
        _rear = _prev(_rear);
26
        return true;
27
    }
28

29
    // ========== 头部操作（双端队列特有）==========
30
    bool insertFront(const T& value) {
31
        if (full()) return false;
32
        _front = _prev(_front);  // front 向前退一步
33
        _buf[_front] = value;
34
        return true;
35
    }
36

37
    bool deleteFront() {
38
        if (empty()) return false;
39
        _front = _next(_front);
40
        return true;
41
    }
42

43
    // ========== 访问 ==========
44
    T& getFront() { return _buf[_front]; }
45
    T& getRear()  { return _buf[_prev(_rear)]; }
46

47
    bool empty() const { return _front == _rear; }
48
    bool full() const  { return _next(_rear) == _front; }
49
    std::size_t size() const { return (_rear + N - _front) % N; }
50
};

1
struct TreeNode {
2
    int val;
3
    TreeNode* left;
4
    TreeNode* right;
5
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
6
};
7

8
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
9
    std::vector<std::vector<int>> result;
10
    if (!root) return result;
11

12
    std::queue<TreeNode*> q;
13
    q.push(root);
14

15
    while (!q.empty()) {
16
        int level_size = q.size();  // 关键：记录当前层的节点数
17
        std::vector<int> level;
18

19
        for (int i = 0; i < level_size; ++i) {
20
            TreeNode* node = q.front();
21
            q.pop();
22

23
            level.push_back(node->val);
24

25
            // 下一层的节点入队
26
            if (node->left)  q.push(node->left);
27
            if (node->right) q.push(node->right);
28
        }
29

30
        result.push_back(std::move(level));
31
    }
32
    return result;
33
}
34
// 时间 O(n)：每个节点进出队列各一次
35
// 空间 O(n)：最坏情况（完全二叉树最后一层有 n/2 个节点）

1
int numIslands(std::vector<std::vector<char>>& grid) {
2
    if (grid.empty()) return 0;
3

4
    int rows = grid.size(), cols = grid[0].size();
5
    int count = 0;
6

7
    // 方向数组——上下左右
8
    constexpr int dx[] = {0, 0, 1, -1};
9
    constexpr int dy[] = {1, -1, 0, 0};
10

11
    for (int i = 0; i < rows; ++i) {
12
        for (int j = 0; j < cols; ++j) {
13
            if (grid[i][j] == '1') {
14
                ++count;
15
                grid[i][j] = '0';  // 标记为已访问
16

17
                // BFS 扩散
18
                std::queue<std::pair<int, int>> q;
19
                q.push({i, j});
20

21
                while (!q.empty()) {
22
                    auto [x, y] = q.front();
23
                    q.pop();
24

25
                    for (int d = 0; d < 4; ++d) {
26
                        int nx = x + dx[d];
27
                        int ny = y + dy[d];
28
                        if (nx >= 0 && nx < rows && ny >= 0 && ny < cols
29
                            && grid[nx][ny] == '1') {
30
                            grid[nx][ny] = '0';  // 入队时就标记！
31
                            q.push({nx, ny});
32
                        }
33
                    }
34
                }
35
            }
36
        }
37
    }
38
    return count;
39
}
40
// 时间 O(M×N), 空间 O(min(M, N))

1
std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
2
    std::vector<int> result;
3
    std::deque<int> dq;  // 存下标，对应的值单调递减
4

5
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
6
        // 1. 移除队头过期的元素（出了窗口范围）
7
        while (!dq.empty() && dq.front() <= i - k) {
8
            dq.pop_front();
9
        }
10

11
        // 2. 维护单调性：新元素比队尾大，队尾永远不可能是答案了
12
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
13
            dq.pop_back();
14
        }
15

16
        // 3. 新元素入队
17
        dq.push_back(i);
18

19
        // 4. 窗口形成后，队头就是最大值
20
        if (i >= k - 1) {
21
            result.push_back(nums[dq.front()]);
22
        }
23
    }
24
    return result;
25
}
26
// 时间 O(n)：每个元素最多入队一次、出队一次
27
// 空间 O(k)

1
int leastInterval(std::vector<char>& tasks, int n) {
2
    // 贪心策略：每个时间段优先执行剩余数量最多的任务
3
    std::array<int, 26> freq{};
4
    for (char t : tasks) ++freq[t - 'A'];
5

6
    // 最大堆：按剩余次数排序
7
    std::priority_queue<int> pq;
8
    for (int f : freq) {
9
        if (f > 0) pq.push(f);
10
    }
11

12
    int time = 0;
13

14
    while (!pq.empty()) {
15
        std::vector<int> cooldown;  // 本轮执行后需要冷却的任务
16

17
        // 一个冷却周期 = n + 1 个时间段
18
        for (int i = 0; i <= n; ++i) {
19
            if (!pq.empty()) {
20
                int remaining = pq.top() - 1;  // 执行一次
21
                pq.pop();
22
                if (remaining > 0) {
23
                    cooldown.push_back(remaining);
24
                }
25
            }
26
            ++time;
27

28
            // 如果所有任务都做完了，提前退出
29
            if (pq.empty() && cooldown.empty()) break;
30
        }
31

32
        // 冷却完毕，重新入堆
33
        for (int r : cooldown) pq.push(r);
34
    }
35

36
    return time;
37
}
38
// 时间 O(n × |tasks|), 空间 O(26) = O(1)

1
class MyStack {
2
    std::queue<int> _q;
3

4
public:
5
    // 核心技巧：push 时把新元素"翻"到队列头部
6
    void push(int x) {
7
        _q.push(x);
8
        // 把前面所有元素搬到 x 后面
9
        for (int i = 0; i < static_cast<int>(_q.size()) - 1; ++i) {
10
            _q.push(_q.front());
11
            _q.pop();
12
        }
13
    }
14

15
    int pop() {
16
        int val = _q.front();
17
        _q.pop();
18
        return val;
19
    }
20

21
    int top()   { return _q.front(); }
22
    bool empty() { return _q.empty(); }
23
};
24
// push: O(n), pop/top: O(1)
25
// 用一个队列就够了！

1
#include <queue>
2
#include <variant>
3
#include <functional>
4
#include <unordered_map>
5
#include <vector>
6
#include <string>
7

8
// ===== 事件类型定义 =====
9
struct InputEvent {
10
    enum class Type { KeyDown, KeyUp, MouseMove, MouseClick };
11
    Type type;
12
    int  key_code;
13
    float mouse_x, mouse_y;
14
};
15

16
struct CollisionEvent {
17
    uint32_t entity_a;
18
    uint32_t entity_b;
19
    float    impact_force;
20
};
21

22
struct DamageEvent {
23
    uint32_t source;
24
    uint32_t target;
25
    float    amount;
26
    std::string damage_type;  // "physical", "magical", "true"
27
};
28

29
struct AudioEvent {
30
    std::string sound_name;
31
    float volume;
32
    float x, y;  // 3D 位置
33
};
34

35
// 使用 std::variant 统一所有事件类型
36
using GameEvent = std::variant<InputEvent, CollisionEvent, DamageEvent, AudioEvent>;
37

38
// ===== 事件队列 =====
39
class EventQueue {
40
    std::queue<GameEvent> _queue;
41

42
public:
43
    // 任何系统都可以发布事件
44
    template <typename E>
45
    void publish(E&& event) {
46
        _queue.push(std::forward<E>(event));
47
    }
48

49
    // 每帧统一处理
50
    void process_all(auto&& handler) {
51
        while (!_queue.empty()) {
52
            std::visit(handler, _queue.front());
53
            _queue.pop();
54
        }
55
    }
56

57
    std::size_t pending() const { return _queue.size(); }
58
    bool empty() const { return _queue.empty(); }
59
};
60

61
// ===== 使用示例 =====
62
class GameEngine {
63
    EventQueue _events;
64

65
public:
66
    void update(float dt) {
67
        // 1. 各子系统产生事件
68
        poll_input();
69
        update_physics(dt);
70
        update_ai(dt);
71

72
        // 2. 统一处理所有事件
73
        _events.process_all([this](auto&& event) {
74
            using T = std::decay_t<decltype(event)>;
75

76
            if constexpr (std::is_same_v<T, DamageEvent>) {
77
                apply_damage(event);
78
            } else if constexpr (std::is_same_v<T, CollisionEvent>) {
79
                handle_collision(event);
80
            } else if constexpr (std::is_same_v<T, AudioEvent>) {
81
                play_sound(event);
82
            } else if constexpr (std::is_same_v<T, InputEvent>) {
83
                handle_input(event);
84
            }
85
        });
86

87
        // 3. 渲染
88
        render();
89
    }
90

91
    // 物理系统检测到碰撞 → 发布事件（而不是直接处理）
92
    void update_physics(float dt) {
93
        // ... 碰撞检测 ...
94
        // if (collision_detected) {
95
        //     _events.publish(CollisionEvent{id_a, id_b, force});
96
        //     _events.publish(DamageEvent{id_a, id_b, 25.0f, "physical"});
97
        //     _events.publish(AudioEvent{"hit_sound", 0.8f, x, y});
98
        // }
99
    }
100

101
    // 以下为简化声明
102
    void poll_input() {}
103
    void update_ai(float) {}
104
    void apply_damage(const DamageEvent&) {}
105
    void handle_collision(const CollisionEvent&) {}
106
    void play_sound(const AudioEvent&) {}
107
    void handle_input(const InputEvent&) {}
108
    void render() {}
109
};

1
#include <queue>
2
#include <variant>
3
#include <cstdint>
4
#include <array>
5

6
// ===== 渲染命令定义 =====
7
struct ClearCommand {
8
    float r, g, b, a;
9
};
10

11
struct DrawMeshCommand {
12
    uint32_t mesh_id;
13
    uint32_t material_id;
14
    std::array<float, 16> transform;  // 4x4 矩阵（列主序）
15
};
16

17
struct SetViewportCommand {
18
    int x, y, width, height;
19
};
20

21
struct DrawUICommand {
22
    uint32_t texture_id;
23
    float x, y, w, h;    // 屏幕坐标矩形
24
    float u0, v0, u1, v1; // UV 坐标
25
};
26

27
struct SetBlendModeCommand {
28
    enum class Mode { Opaque, Alpha, Additive };
29
    Mode mode;
30
};
31

32
using RenderCommand = std::variant<
33
    ClearCommand,
34
    DrawMeshCommand,
35
    SetViewportCommand,
36
    DrawUICommand,
37
    SetBlendModeCommand
38
>;
39

40
// ===== 渲染命令队列 =====
41
class RenderCommandBuffer {
42
    std::queue<RenderCommand> _commands;
43

44
public:
45
    template <typename Cmd>
46
    void submit(Cmd&& cmd) {
47
        _commands.push(std::forward<Cmd>(cmd));
48
    }
49

50
    // 渲染线程按顺序执行所有命令
51
    void execute(auto&& gpu) {
52
        while (!_commands.empty()) {
53
            std::visit(gpu, _commands.front());
54
            _commands.pop();
55
        }
56
    }
57

58
    void clear() {
59
        std::queue<RenderCommand> empty;
60
        std::swap(_commands, empty);
61
    }
62

63
    std::size_t command_count() const { return _commands.size(); }
64
};

1
// 逻辑线程：录制渲染命令（不涉及 GPU 调用）
2
RenderCommandBuffer cmd_buf;
3

4
cmd_buf.submit(ClearCommand{0.1f, 0.1f, 0.15f, 1.0f});
5
cmd_buf.submit(SetViewportCommand{0, 0, 1920, 1080});
6

7
// 渲染所有不透明物体
8
cmd_buf.submit(SetBlendModeCommand{SetBlendModeCommand::Mode::Opaque});
9
for (auto& obj : opaque_objects) {
10
    cmd_buf.submit(DrawMeshCommand{obj.mesh, obj.material, obj.transform});
11
}
12

13
// 渲染半透明物体
14
cmd_buf.submit(SetBlendModeCommand{SetBlendModeCommand::Mode::Alpha});
15
for (auto& obj : transparent_objects) {
16
    cmd_buf.submit(DrawMeshCommand{obj.mesh, obj.material, obj.transform});
17
}
18

19
// UI 最后渲染
20
for (auto& ui : ui_elements) {
21
    cmd_buf.submit(DrawUICommand{ui.texture, ui.rect.x, ui.rect.y,
22
                                  ui.rect.w, ui.rect.h,
23
                                  0, 0, 1, 1});
24
}
25

26
// 渲染线程：执行命令（实际调用 GPU API）
27
// cmd_buf.execute(gpu_backend);

1
#include <queue>
2
#include <mutex>
3
#include <optional>
4
#include <vector>
5
#include <cstdint>
6

7
struct NetworkMessage {
8
    uint16_t type;
9
    uint32_t sender_id;
10
    std::vector<uint8_t> payload;
11
    double   timestamp;
12
};
13

14
// 线程安全的消息队列（网络线程写入，逻辑线程读取）
15
class MessageQueue {
16
    std::queue<NetworkMessage> _queue;
17
    mutable std::mutex _mutex;
18

19
    // 防止单帧处理太多消息导致卡顿
20
    static constexpr int MAX_MESSAGES_PER_FRAME = 100;
21

22
public:
23
    // 网络线程调用——线程安全推入
24
    void push(NetworkMessage msg) {
25
        std::lock_guard lock(_mutex);
26
        _queue.push(std::move(msg));
27
    }
28

29
    // 逻辑线程调用——批量取出（限制数量）
30
    std::vector<NetworkMessage> drain(int max_count = MAX_MESSAGES_PER_FRAME) {
31
        std::lock_guard lock(_mutex);
32
        std::vector<NetworkMessage> batch;
33

34
        int count = std::min(max_count, static_cast<int>(_queue.size()));
35
        batch.reserve(count);
36

37
        for (int i = 0; i < count; ++i) {
38
            batch.push_back(std::move(_queue.front()));
39
            _queue.pop();
40
        }
41
        return batch;
42
    }
43

44
    std::size_t pending() const {
45
        std::lock_guard lock(_mutex);
46
        return _queue.size();
47
    }
48
};
49

50
// ===== 游戏逻辑中使用 =====
51
class NetworkManager {
52
    MessageQueue _incoming;
53

54
public:
55
    // 每帧调用
56
    void process_messages() {
57
        auto messages = _incoming.drain();
58

59
        for (auto& msg : messages) {
60
            switch (msg.type) {
61
                case 0x01: handle_player_move(msg); break;
62
                case 0x02: handle_spawn_entity(msg); break;
63
                case 0x03: handle_chat_message(msg); break;
64
                case 0x04: handle_damage_sync(msg); break;
65
                default: break;
66
            }
67
        }
68
    }
69

70
    // 网络线程回调
71
    void on_message_received(NetworkMessage msg) {
72
        _incoming.push(std::move(msg));
73
    }
74

75
private:
76
    void handle_player_move(const NetworkMessage&) {}
77
    void handle_spawn_entity(const NetworkMessage&) {}
78
    void handle_chat_message(const NetworkMessage&) {}
79
    void handle_damage_sync(const NetworkMessage&) {}
80
};