• 【数据结构】线性表（十一）队列：双端队列及其基本操作（初始化、判空、判满、头部入队、尾部入队、头部出队、尾部出队、存取队首队尾元素）

    文章目录

    一、队列

    1. 定义

      队列是一种操作受限的线性表，对于它的所有插入都在表的一端进行，所有的删除（以至几乎所有的存取）都在表的另一端进行，且这些操作又都是按照先进先出（FIFO）的原则进行的。进行删除的一端称为队头（front），进行插入的一端称为队尾（rear）。没有元素的队列称为空队列（简称空队）。

    在这里插入图片描述
      队列就像生活中排队购物，新来的人只能加入队尾（假设不允许插队），购物结束后先离开的总是队头（假设无人中途离队）。也就是说，先加入队列的成员总是先离开队列，因此队列被称为先进先出（First In First Out）的线性表，简称为FIFO表。如图，在空队列中依次加入元素a1，a2，a3，a4，a5，出队次序仍然是a1，a2，a3，a4，a5 .

    2. 基本操作

    • 队列是受限的线性表，其基本操作包括

      • IsEmpty() : 判断队列是否为空；
      • isFull()：判断队列是否为满；
      • enqueue() ：向队尾添加元素（入队）；
      • dequeue() ：删除队首元素（出队）；
      • peek()：获取队首的元素值（存取）；

    • 同普通线性表一样，队列也可以用顺序存储和链接存储两种方式来实现：

    二、顺序队列

      参考前文：【数据结构】线性表（八）队列：顺序队列及其基本操作（初始化、判空、判满、入队、出队、存取队首元素）

    三、链式队列

      参考前文：【数据结构】线性表（九）队列：链式队列及其基本操作（初始化、判空、入队、出队、存取队首元素）

    双端队列

      双端队列（Double-ended Queue，简称Deque）可以在队列的头部和尾部进行元素的插入和删除操作，因此可以看作是一种特殊的队列和栈的结合。

    双端队列的操作包括：

    • 在队列头部插入元素（头部入队）；
    • 在队列尾部插入元素（尾部入队）；
    • 在队列头部删除元素（头部出队），并返回该元素；
    • 在队列尾部删除元素（尾部出队），并返回该元素；
    • 获取队列头部的元素，但不删除它；
    • 获取队列尾部的元素，但不删除它；
    • 判断队列是否为空。

      双端队列可以用于解决一些特定的问题，例如实现滑动窗口最大值、字符串处理等。它的灵活性使得在某些场景下比普通队列更加方便和高效。
    图片来源于网络，侵删

    0. 头文件

    #include 
#include 

    • 1
    • 2
    • 两个头文件
      • stdio.h用于输入输出操作
      • stdlib.h用于内存分配和释放

    1. 队列结构体

    typedef struct {
    int* elements;  // 存储队列元素的数组
    int front;      // 队列头部索引
    int rear;       // 队列尾部索引
    int size;       // 队列的最大容量
} Deque;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    2. 初始化

    void initDeque(Deque* deque, int capacity) {
    deque->elements = (int*)malloc(capacity * sizeof(int));
    deque->front = -1;
    deque->rear = -1;
    deque->size = capacity;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 使用动态内存分配函数 malloc 分配了一个大小为 capacity * sizeof(int) 的整型数组，并将其地址赋值给 deque->elements。
    • 将 deque->front 和 deque->rear 初始化为 -1，表示队列为空。
    • 将 deque->size 设置为传入的容量值。

    3. 判断队列是否为空

    int isEmpty(Deque* deque) {
    return deque->front == -1;
}

    • 1
    • 2
    • 3

      通过检查队列的头部索引是否为-1来判断队列是否为空。

    4. 判断队列是否已满

    int isFull(Deque* deque) {
    return deque->rear == deque->size - 1;
}

    • 1
    • 2
    • 3

      通过检查队列的尾部索引是否等于队列的最大容量减1来判断队列是否已满。

    5. 头部入队

    void insertFront(Deque* deque, int element) {
    if (isEmpty(deque)) {
        deque->front = 0;
        deque->rear = 0;
    } else if (deque->front == 0) {
        deque->front = deque->size - 1;
    } else {
        deque->front--;
    }
    deque->elements[deque->front] = element;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 如果队列为空（即 isEmpty(deque) 返回真），则将队列头部和尾部索引都设置为 0。
    • 否则，如果队列头部索引为 0，则将其设置为队列的最大容量减 1，否则将其递减 1。
    • 将元素 element 存储到队列头部索引对应的位置。

    6. 尾部入队

    void insertRear(Deque* deque, int element) {
    if (isEmpty(deque)) {
        deque->front = 0;
        deque->rear = 0;
    } else if (deque->rear == deque->size - 1) {
        deque->rear = 0;
    } else {
        deque->rear++;
    }
    deque->elements[deque->rear] = element;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 如果队列为空（即 isEmpty(deque) 返回真），则将队列头部和尾部索引都设置为 0。
    • 否则，如果队列尾部索引等于队列的最大容量减 1，则将其设置为 0，否则将其递增 1。
    • 将元素 element 存储到队列尾部索引对应的位置。

    7. 头部出队

    void deleteFront(Deque* deque) {
    if (isEmpty(deque)) {
        return;
    }
    if (deque->front == deque->rear) {
        deque->front = -1;
        deque->rear = -1;
    } else if (deque->front == deque->size - 1) {
        deque->front = 0;
    } else {
        deque->front++;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 如果队列为空（即 isEmpty(deque) 返回真），则直接返回，不进行任何操作。
    • 否则，如果队列头部索引等于队列尾部索引，表示队列中只有一个元素，将队列头部和尾部索引都设置为 -1。
    • 否则，如果队列头部索引等于队列的最大容量减 1，则将其设置为 0，否则将其递增 1。

    8. 尾部出队

    void deleteRear(Deque* deque) {
    if (isEmpty(deque)) {
        return;
    }
    if (deque->front == deque->rear) {
        deque->front = -1;
        deque->rear = -1;
    } else if (deque->rear == 0) {
        deque->rear = deque->size - 1;
    } else {
        deque->rear--;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 如果队列为空（即 isEmpty(deque) 返回真），则直接返回，不进行任何操作。
    • 否则，如果队列尾部索引等于队列头部索引，表示队列中只有一个元素，将队列头部和尾部索引都设置为 -1。
    • 否则，如果队列尾部索引等于 0，则将其设置为队列的最大容量减 1，否则将其递减 1。

    9. 存取队列头部的元素

    int getFront(Deque* deque) {
    if (isEmpty(deque)) {
        return -1;  // 队列为空时返回一个特定的值，可以根据实际情况进行修改
    }
    return deque->elements[deque->front];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 如果队列为空（即 isEmpty(deque) 返回真），则返回一个特定的值（这里是 -1），表示队列为空。
    • 否则，返回队列头部索引对应的元素。

    10. 存取队列尾部的元素

    int getRear(Deque* deque) {
    if (isEmpty(deque)) {
        return -1;  // 队列为空时返回一个特定的值，可以根据实际情况进行修改
    }
    return deque->elements[deque->rear];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 如果队列为空（即 isEmpty(deque) 返回真），则返回一个特定的值（这里是 -1），表示队列为空。
    • 否则，返回队列尾部索引对应的元素。

    11. 释放队列内存

    void freeDeque(Deque* deque) {
    free(deque->elements);
}

    • 1
    • 2
    • 3

      使用 free 函数释放 deque->elements 指向的动态内存。

    12. 主函数

    int main() {
    Deque deque;
    int capacity = 5;  // 设置队列的容量

    // 初始化双端队列
    initDeque(&deque, capacity);

    // 在队列头部插入元素
    insertFront(&deque, 1);
    insertFront(&deque, 2);

    // 在队列尾部插入元素
    insertRear(&deque, 3);
    insertRear(&deque, 4);

    // 获取队列头部和尾部的元素
    printf("Front: %d\n", getFront(&deque));
    printf("Rear: %d\n", getRear(&deque));

    // 在队列头部删除元素
    deleteFront(&deque);

    // 在队列尾部删除元素
    deleteRear(&deque);

    // 获取更新后的队列头部和尾部的元素
    printf("Front: %d\n", getFront(&deque));
    printf("Rear: %d\n", getRear(&deque));

    // 释放队列内存
    freeDeque(&deque);

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    在这里插入图片描述

    13. 代码整合

    #include 
#include 

typedef struct {
    int* elements;  // 存储队列元素的数组
    int front;      // 队列头部索引
    int rear;       // 队列尾部索引
    int size;       // 队列的最大容量
} Deque;

void initDeque(Deque* deque, int capacity) {
    deque->elements = (int*)malloc(capacity * sizeof(int));
    deque->front = -1;
    deque->rear = -1;
    deque->size = capacity;
}

int isEmpty(Deque* deque) {
    return deque->front == -1;
}

int isFull(Deque* deque) {
    return deque->rear == deque->size - 1;
}

void insertFront(Deque* deque, int element) {
    if (isEmpty(deque)) {
        deque->front = 0;
        deque->rear = 0;
    } else if (deque->front == 0) {
        deque->front = deque->size - 1;
    } else {
        deque->front--;
    }
    deque->elements[deque->front] = element;
}

void insertRear(Deque* deque, int element) {
    if (isEmpty(deque)) {
        deque->front = 0;
        deque->rear = 0;
    } else if (deque->rear == deque->size - 1) {
        deque->rear = 0;
    } else {
        deque->rear++;
    }
    deque->elements[deque->rear] = element;
}

void deleteFront(Deque* deque) {
    if (isEmpty(deque)) {
        return;
    }
    if (deque->front == deque->rear) {
        deque->front = -1;
        deque->rear = -1;
    } else if (deque->front == deque->size - 1) {
        deque->front = 0;
    } else {
        deque->front++;
    }
}

void deleteRear(Deque* deque) {
    if (isEmpty(deque)) {
        return;
    }
    if (deque->front == deque->rear) {
        deque->front = -1;
        deque->rear = -1;
    } else if (deque->rear == 0) {
        deque->rear = deque->size - 1;
    } else {
        deque->rear--;
    }
}

int getFront(Deque* deque) {
    if (isEmpty(deque)) {
        return -1;  // 队列为空时返回一个特定的值，可以根据实际情况进行修改
    }
    return deque->elements[deque->front];
}

int getRear(Deque* deque) {
    if (isEmpty(deque)) {
        return -1;  // 队列为空时返回一个特定的值，可以根据实际情况进行修改
    }
    return deque->elements[deque->rear];
}

void freeDeque(Deque* deque) {
    free(deque->elements);
}

int main() {
    Deque deque;
    int capacity = 5;  // 设置队列的容量

    // 初始化双端队列
    initDeque(&deque, capacity);

    // 在队列头部插入元素
    insertFront(&deque, 1);
    insertFront(&deque, 2);

    // 在队列尾部插入元素
    insertRear(&deque, 3);
    insertRear(&deque, 4);

    // 获取队列头部和尾部的元素
    printf("Front: %d\n", getFront(&deque));
    printf("Rear: %d\n", getRear(&deque));

    // 在队列头部删除元素
    deleteFront(&deque);

    // 在队列尾部删除元素
    deleteRear(&deque);

    // 获取更新后的队列头部和尾部的元素
    printf("Front: %d\n", getFront(&deque));
    printf("Rear: %d\n", getRear(&deque));

    // 释放队列内存
    freeDeque(&deque);

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
  • 相关阅读:
    一篇五分生信临床模型预测文章代码复现——Figure 3. 基因富集分析（一）
    烟台-青岛五日游
    【python】算法与数据结构例题分析
    论文阅读--基于编码器-解码器的卷积神经网络与多尺度感知模块用于人群计数
    Day23_8 Java学习之多线程安全、死锁及状态
    数据中心液冷服务器详情说明
    微信小程序关注公众号
    Java中类的内部成员之五： 内部类
    Vue3学习：如何在Vue3项目中创建一个axios实例
    C++——异常
  • 原文地址：https://blog.csdn.net/m0_63834988/article/details/133947698