一、933 最近的请求次数：队列题

题目要求每次 ping(t) 返回 [t-3000, t] 范围内的请求次数。因为请求时间 t 是递增的，所以可以用队列维护最近 3000ms 内的请求。

1. 核心概念

每次来了一个新时间 t：

1. 把 t 入队
2. 把小于 t - 3000 的旧请求出队
3. 队列长度就是答案

队列里始终保存：
最近 3000ms 内的请求时间

2. 为什么用队列？

因为时间是递增的。

旧请求一定在队头，新请求一定从队尾进。

所以：

队尾入队新请求
队头删除过期请求

正好是 FIFO 队列。

3. C代码模板
#include <stdlib.h>

struct RecentCounter {
    int data[10010];
    int front;
    int rear;
};

struct RecentCounter* recentCounterCreate() {
    struct RecentCounter* obj = malloc(sizeof(struct RecentCounter));
    obj->front = 0;
    obj->rear = 0;
    return obj;
}

int recentCounterPing(struct RecentCounter* obj, int t) {
    //让最新的t入队，然后移动rear
    obj->data[obj->rear] = t;
    obj->rear++;

    while (obj->front < obj->rear && obj->data[obj->front] < t - 3000) {
    //当front对应的data小于t-3000时，就出队    
        obj->front++;
    }

    return obj->rear - obj->front;
}

void recentCounterFree(struct RecentCounter* obj) {
    free(obj);
}

4. 例子
ping(1)
队列：[1]
范围：[-2999, 1]
答案：1

ping(100)
队列：[1, 100]
范围：[-2900, 100]
答案：2

ping(3001)
队列：[1, 100, 3001]
范围：[1, 3001]
答案：3

ping(3002)
先入队：[1, 100, 3001, 3002]
范围：[2, 3002]
1 过期，出队
队列：[100, 3001, 3002]
答案：3

5. 易错点
过期条件是：
data[front] < t - 3000

不是 <=

因为 [t-3000, t] 是闭区间，
等于 t-3000 的请求还有效。

二、844 比较含退格的字符串：栈题

题目给两个字符串 s 和 t，# 表示退格，要求判断两个字符串经过退格处理后是否相等。

1. 核心概念

遇到普通字符：入栈

遇到 #：如果栈非空，就弹出栈顶

最后栈里剩下的字符就是处理后的字符串。

2. 为什么用栈？

退格删除的是：前一个字符

也就是最近加入的字符。

这正好符合栈：

后进先出 LIFO

3. 固定模板
遍历字符串：

如果是普通字符：
    push

如果是 #：
    如果栈不空：
        pop

最后比较两个栈中的内容
4. C代码
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

char* build(char* s) {
    int n = strlen(s);
    char* stack = malloc((n + 1) * sizeof(char));
    int top = 0;

    for (int i = 0; i < n; i++) {
        if (s[i] != '#') {
            stack[top] = s[i];
            top++;
        } else {
            if (top > 0) {
                top--;
            }
        }
    }

    stack[top] = '\0';

    return stack;
}

bool backspaceCompare(char* s, char* t) {
    char* a = build(s);
    char* b = build(t);

    bool ans = strcmp(a, b) == 0;

    free(a);
    free(b);

    return ans;
}

5. 例子
s = "ab#c"

处理过程：

a 入栈：[a]
b 入栈：[a, b]
# 删除 b：[a]
c 入栈：[a, c]

最终：

"ac"
t = "ad#c"

处理过程：

a 入栈：[a]
d 入栈：[a, d]
# 删除 d：[a]
c 入栈：[a, c]

最终：
"ac"

所以：
true

6. 易错点
1. 遇到 # 时，如果栈为空，不能继续 pop。
2. C字符串最后必须补 '\0'。
3. top 表示下一个可插入位置，不是栈顶元素下标。

三、两题总结

933 最近请求次数：
结构：
    队列
原因：
    旧请求先过期，先出队
操作：
    队尾入队
    队头删除过期元素

--------------------------------

844 退格字符串比较：
结构：
    栈
原因：
    退格删除最近输入的字符
操作：
    普通字符入栈
    # 弹出栈顶

队列解决“先进先出”的时间窗口问题；栈解决“后进先出”的撤销/退格问题。