队列

---

基本概念

1. 队列是一种先进先出（FIFO）的数据结构。
2. 对于队列来说，表尾端称为队尾（tail），表头端称为队头（front）。
3. 所有元素只能从队尾进入，进入队列的操作称为入队。
4. 同时所有元素只能从队头弹出，弹出队列的操作称为出队。
5. 因为只能对队头或队尾元素进行操作，因此不支持对队列内元素进行随机访问，即我们不能在任意位置访问队列内元素，只能从队头或队尾访问。

---

入队出队图片演示

---

队列的基本操作

1. 队头（队尾）指针：指向队头（队尾）下标。注意队头队尾区间是一个左闭右开区间。
2. 入队：即将元素放入队列，同时队尾指针+1，注意要判断队列是否满，如果是则需要将队列扩容或者禁止入队列。
3. 出队列：即将队列顶元素弹出，同时队头指针+1，注意要判断队列是否为空，如果队列为空仍然出队会报错。
4. 判断队列是否为空：返回是或否。
5. 计算队列中元素数量：返回队列中元素数量。

---

代码示例

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//自定义队列结构
typedef struct my_queue
{
    int front, tail;
    int size;
    int* data;
}my_queue;
//初始化队列
my_queue* init_queue(int num)
{
    my_queue* t = (my_queue*)malloc(sizeof(my_queue));
    t -> front = 0;
    t -> tail = 0;
    t -> size = num;
    t -> data = (int*)malloc(sizeof(int) * num);
    return t;
}
//入队操作
//返回值：1成功，0失败
int queue_push(my_queue* que, int num)
{
    if(que -> tail == que -> size) return 0;
    que -> data[que -> tail++] = num;
    return 1;
}
//出队操作
int queue_pop(my_queue* que)
{
   return que -> data[que -> front++];
}
//判断队列为空
//返回值：1真，0假
int queue_is_empty(my_queue* que)
{
    if(que -> front == que -> tail) return 1;
    return 0;
}
//计算队列中元素数量
int queue_size(my_queue* que)
{
    return que -> tail - que -> front;
}
int main()
{
    my_queue* que = init_queue(10);
    //队列操作测试
    srand(time(0));
    int n;
    printf("请输入测试次数：\n");
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int op = rand() % 3;
        switch(op)
        {
            //入队
            case 0:
            {
                if(queue_push(que, i))
                    printf("元素 %d 入队成功！\n", i);
                else printf("入队失败！\n");
                break;
            }
            //出队
            case 1:
            {
                if(queue_is_empty(que)) break;
                printf("出队元素为%d\n", queue_pop(que));
                break;
            }
            //读元素数量
            case 2:
            {
                printf("队列中元素数量为：%d\n", queue_size(que));
                break;
            }
        }
    }
    return 0;
}

---

相关题目

• 海贼OJ 284.报数

• 海贼OJ 284.海港

• LeetCode 225. 用队列实现栈

循环队列

有一天本蒟蒻用队列用着用着发现，明明队列中还有存放元素的位置，但是此时我们却无法存放元素了。（如下图所示）

遇到这种情况，本蒟蒻表示大吃一斤（bushi）：照这么进行下去，我这个队列利用率不是肥肠肥肠低了吗？于是请教老师后，老师告诉我说可以用循环队列解决。

---

基本概念

• 和队列概念相同

---

循环队列基本操作

1. 队头（队尾）指针：指向队头（队尾）下标。注意：（1）队头队尾区间是一个左闭右开区间 （2）队列满时，一种解决与空队冲突方案是——队尾指针应在队头指针前一个位置（不然就会分不清到底是空队还是满队），即（队尾指针 + 1） % 队列大小 = 队头指针
2. 入队：即将元素放入队列，同时队尾指针+1 后再模队列大小（注意非元素数量），注意要判断队列是否满，如果是则需要将队列扩容或者禁止入队列。
3. 出队列：即将队列顶元素弹出，同时队头指针+1后再模队列大小（注意非元素数量），注意要判断队列是否为空，如果队列为空仍然出队会报错。
4. 判断队列是否为空：返回是或否。
5. 计算队列中元素数量：返回队列中元素数量。

• tips 1：为什么队头队尾+1后要模上队列大小？——如果指针指向了队尾，那么该操作就可以将其重新指向队头，从而实现循环链表。
• tips 2：怎样判断队列是否为满？——（1）添加标志位特殊判断，（2）队尾指针在队头指针前一位即为队列满（如果与队头指针重合，无法判断该队列为空还是为满）
• tips 3：怎样返回对列中的元素数量？——可以分两种情况，队尾小于队头的话可以返回队尾指针 + 队列大小 - 队头指针。

---

入队出队图片演示

代码示例

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//自定义队列结构
typedef struct my_queue
{
    int front, tail;
    int size;
    int* data;
}my_queue;
//初始化队列
my_queue* init_queue(int num)
{
    my_queue* t = (my_queue*)malloc(sizeof(my_queue));
    t -> front = 0;
    t -> tail = 0;
    t -> size = num;
    t -> data = (int*)malloc(sizeof(int) * num);
    return t;
}
//入队操作
//返回值：1成功，0失败
int queue_push(my_queue* que, int num)
{
    if((que -> tail + 1) % que -> size == que -> front) return 0;
    que -> data[que -> tail] = num;
    que -> tail = (que -> tail + 1) % que -> size;
    return 1;
}
//出队操作
int queue_pop(my_queue* que)
{
    int res = que -> data[que -> front];
    que -> front = (que -> front + 1) % que -> size;
    return res;
}
//判断队列为空
//返回值：1真，0假
int queue_is_empty(my_queue* que)
{
    if(que -> front == que -> tail) return 1;
    return 0;
}
//计算队列中元素数量
int queue_size(my_queue* que)
{
    if(que -> tail < que -> front)
        return que -> tail + que -> size - que -> front;
    return que -> tail - que -> front;
}
int main()
{
    my_queue* que = init_queue(2);
    //队列操作测试
    srand(time(0));
    int n;
    printf("请输入测试次数：\n");
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int op = rand() % 3;
        switch(op)
        {
            //入队
            case 0:
            {
                if(queue_push(que, i))
                    printf("元素 %d 入队成功！\n", i);
                else printf("入队失败！\n");
                break;
            }
            //出队
            case 1:
            {
                if(queue_is_empty(que)) break;
                printf("出队元素为%d\n", queue_pop(que));
                break;
            }
            //读元素数量
            case 2:
            {
                printf("队列中元素数量为：%d\n", queue_size(que));
                break;
            }
        }
    }
    return 0;
}

单调队列

---

基本概念

• 我们有这么一个队列，栈内元素要么（非严格）单调递增，要么（非严格）单调递减，那么这个队列就是单调队列
• （没了，还是这么朴实无华且枯燥你敢信（bushi））

---

图解维护单调队列

---

相关题目

本蒟蒻遇到的使用单调队列的题好少额QAQ，就把之前遇到的几个拿出来吧，后续再遇到单调队列的再继续更新相关题目吧！

• LeetCode 239. 滑动窗口最大值

• LeetCode 1438. 绝对差不超过限制的最长连续子数组