队列

前言

在生活中，我们多多少少都因为一些原因排过队，而在数据处理的过程中，我们也有需要给数据排队的情况，如实现一个病人看病的程序，我们就需要给病人进行排队，然后依次进行。为此我们引入一种新的数据结构——队列

基本概念和常用操作的时间复杂度

队列是线性表数据结构的一种，是只允许在一端插入数据操作，在另一端进行删除数据操作的特殊线性表。在通常情况下，队列中的元素无法直接访问。

插入	查找	删除
$O(1)$	$O(n)$	$O(1)$

严格来讲，队列并不能查找元素

队列

graph LR
    队首-->数据1
    数据1--> 数据2
    数据2--> 数据3
    数据3--> 数据4
    队尾-->数据4

队列的构造

队列和链表类似，是可变长度的，为此，我们仍然需要动态分配空间给元素。我们可以基于现成的双向链表，在双向链表的基础上进行修改，将其插入的逻辑改为只能在末尾插入，删除的逻辑改为只能在队列头删除。如果你不了解队列，请点击这里

前置：双向链表的节点类型，队列长度的表示

//节点类型
struct node {
    struct node *next, *prev;
    int data;
} *head, *end;
//记录队列的长度
unsigned long long length = 0;

在队尾插入数据（入队）

//用于插入节点
void push(int data) {
    //队列的长度+1
    length++;
    //新建一个节点
    node *tmp = (node *)malloc(sizeof(node));
    tmp->data = data;
    //新节点的后置指针指向空
    tmp->next = NULL;
    //若长度为0，则自己就是队头
    if(length - 1 == 0) {
        tmp->prev = NULL;
        head = end = tmp;
        return;
    }

    //新节点的前置指针指向队尾
    tmp->prev = end;
    //更新队尾
    end->next = tmp;
    end = tmp;
}

在队头删除数据（出队）

//用于删除节点
void pop() {
    //如果已经没有元素了，错误处理
    if(length == 0) return;
    //如果只有一个元素
    if(length == 1) {
        //删除这个元素本身
        free(head);
        //并将队头和队尾设为NULL
        head = end = NULL;
        //队列长度更新
        length = 0;
        return;
    }
    /* 如果有2个或2个以上的元素则执行以下代码 */
    //队列的长度-1
    length--;
    //更新队首
    head = head->next;
    //清除空间
    free(head->prev);
    //设置队首
    head->prev = NULL;
}

完整代码

//C语言实现
#include <stdlib.h>
#include <stdio.h>
//节点类型
struct node {
    struct node *next, *prev;
    int data;
} *head, *end;
//记录队列的长度
unsigned long long length = 0;
//用于插入节点
void push(int data) {
    //队列的长度+1
    length++;
    //新建一个节点
    node *tmp = (node *)malloc(sizeof(node));
    tmp->data = data;
    //新节点的后置指针指向空
    tmp->next = NULL;
    //若长度为0，则自己就是队头
    if(length - 1 == 0) {
        tmp->prev = NULL;
        head = end = tmp;
        return;
    }
    //新节点的前置指针指向队尾
    tmp->prev = end;
    //更新队尾
    end->next = tmp;
    end = tmp;
}
//用于删除节点
void pop() {
    //如果已经没有元素了，错误处理
    if(length == 0) return;
    //如果只有一个元素
    if(length == 1) {
        //删除这个元素本身
        free(head);
        //并将队头和队尾设为NULL
        head = end = NULL;
        //队列长度更新
        length = 0;
        return;
    }
    /* 如果有2个或2个以上的元素则执行以下代码 */
    //队列的长度-1
    length--;
    //更新队首
    head = head->next;
    //清除空间
    free(head->prev);
    //设置队首
    head->prev = NULL;
}
//在队列中查找数据为data的元素的节点，返回指向该节点的指针
struct node* find(int data) {
    struct node* tmp = head;
    //循环遍历队列
    while(tmp != NULL) {
        //找到数据，退出循环
        if(tmp->data == data)
            break;
        tmp = tmp->next;
    }
    //返回指向该节点的指针
    return tmp;
}
//用于打印队列
void print() {
    if(length == 0) return;
    struct node* tmp = head;
    while(tmp != NULL) {
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }
    putchar('\n');
}
//队列的内存释放
void freeQueue() {
    if(length == 0) return;
    struct node* tmp = head;
    while(tmp != NULL) {
        struct node* p = tmp;
        tmp = tmp->next;
        free(p);
    }
}
int main() {
    push(10);
    push(102);
    push(12);
    push(1042);
    push(110);
    push(1320);
    push(1410);
    push(13);
    print();
    printf("%d\n", head->data);
    pop();
    printf("%d\n", head->data);
    pop();
    printf("%d\n", head->data);
    pop();
    printf("%d\n", head->data);
    pop();
    printf("%d\n", head->data);
    pop();
    print();
    freeQueue();
    return 0;
}

双向队列

双向队列和队列最大的不同就是，双向队列比队列多出了在队头入队和在队尾出队的功能，具体实现也类似

//在队头入队
void push_front(int data) {
    //队列的长度+1
    length++;
    //新建一个节点
    node *tmp = (node *)malloc(sizeof(node));
    tmp->data = data;
    //新节点的前置指针指向空
    tmp->prev = NULL;
    //若长度为0，则自己就是队头
    if(length - 1 == 0) {
        tmp->next = NULL;
        head = end = tmp;
        return;
    }
    //新节点的前置指针指向队首
    tmp->next = head;
    //更新队首
    head->prev = tmp;
    head = tmp;
}

//在队尾出队
void pop_back() {
    //如果已经没有元素了，错误处理
    if(length == 0) return;
    //如果只有一个元素
    if(length == 1) {
        //删除这个元素本身
        free(head);
        //并将队头和队尾设为NULL
        head = end = NULL;
        //队列长度更新
        length = 0;
        return;
    }
    /* 如果有2个或2个以上的元素则执行以下代码 */
    //队列的长度-1
    length--;
    //更新队尾
    end = end->prev;
    //清除空间
    free(end->next);
    //设置队尾
    end->next = NULL;
}

C++ STL queue队列

在C++中有一种STL容器——std::queue<T>

注意，在使用STL queue的时候需要#include <queue>

这是C++ STL官方实现的队列，那个T填入的是我们作为数据的数据类型

如std::queue<int> q

他不仅实现了上文提及的关于队列的功能，还内置了很多方法(函数)

方法名	功能
push(elem)	在队列尾部插入一个元素
pop()	在队列头部删除一个元素
size()	返回队列的长度
empty()	判断队列是否为空
front()	返回队列头的元素
back()	返回队列尾的元素
emplace(Args &&args…)	在队尾构建新元素

C++ STL deque双向队列

此外，C++还向我们提供了另一种STL容器——std::deque<T>

注意，在使用STL deque的时候需要#include <deque>

这是C++ STL官方实现的双向队列，那个T填入的是我们作为数据的数据类型

如std::deque<int> q

他不仅实现了上文提及的关于双向队列的功能，还内置了很多方法(函数)

具体有什么可以参考该网站