【算法集训】基础数据结构：五、队列

今天这一题需要好好理解，确实有点难，今天就先发这一个明天再发其他的

队列是先进先出的，有两个端口一个进一个出；相比栈来说多了一个口；
可以用链表定义也可以用数组定义

第一题 933. 最近的请求次数

https://leetcode.cn/problems/number-of-recent-calls/description/

https://leetcode.cn/problems/H8086Q/description/
这道题理解上很难，需要花一些时间，我也是看了好久才懂。

题目大意是这样的，每次执行ping命令会传入一个时间t，这个时间是递增的；
我们需要做的是将当前时间t到t之前的3000ms的时间中执行的ping命令的所有次数加起来返回即可。
当然这里第一次调用ping命令答案一定是1；
解题思路：
定义一个队列，这个队列的范围是ping命令一共能执行的次数（题目中给了!）
每次执行ping命令将这个时间节点存起来，和前面存的时间节点相减，如果在3000以内则不进行任何操作，让它留在队列；反之则将该时间节点弹出，不符合要求；
最后只需要返回队列的长度就是3000ms内发生的请求数。

//使用数组模拟队列.
typedef struct {
    int head;
    int hail;
    int data[10001];
} RecentCounter;


RecentCounter* recentCounterCreate() {
    RecentCounter * obj = (RecentCounter *)malloc( sizeof(RecentCounter));
    //求队列长度是(队首-队尾+1)
    obj->head = 0;
    obj->hail = -1;
    return obj;
}

int recentCounterPing(RecentCounter* obj, int t) {
    // 队尾+1,表明队列+1
    obj->data[++obj->hail] = t;
    // 如果给定的当前数hail和前面的一个数之间的差值大于3000就表明不在过去3000ms内,在题目中描述为最近请求次数(即为3000ms内); 
    while( t - obj->data[obj->head] > 3000) {
        //则将队列数-1,就是把head+1即可,可以查看求队列长度方法;
        ++obj->head; 
    }
    // 最后返回的是队列的长度,就是队尾-队头
    return obj->hail - obj->head + 1;
}

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

/**
 * Your RecentCounter struct will be instantiated and called as such:
 * RecentCounter* obj = recentCounterCreate();
 * int param_1 = recentCounterPing(obj, t);
 
 * recentCounterFree(obj);
*/