【数据结构与算法】队列

2790

0. 引言

队列的特点是先进者先出。队列最基本的操作只有两个，入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素。它和栈一样，是一种操作受限的线性表数据结构。队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫顺序队列，用链表实现的队列叫链式队列。如果队列的大小事先确定,则一般用数组来实现。如果队列的大小事先不确定，则一般是用链式队列。

1. 用数组实现队列

首先，用数组实现的队列的数据结构如下:

typedef struct tagarray_queue {
    int capacity; // 队列的大小
    int head; // 队头的位置
    int tail; // 队尾的下一个位置
    int *data; // 数据存储区
} array_queue;
复制代码

这里需要注意两点: (1) 我们这里假设存储的数据data是int类型的数据，但其实在实际的开发过程中一般不是int类型。 (2) 注意tail表示的含义:队尾的下一个位置。

首先，创建一个队列:

array_queue *create_queue(int size) {
    if (size <= 0) {
        return NULL;
    }
    array_queue *queue = (array_queue *)malloc(sizeof(array_queue));
    if (queue == NULL) {
        return NULL;
    }
    queue->data = (int *)malloc(size * sizeof(int));
    if (queue->data == NULL) {
        free(queue);
        queue = NULL;
        return NULL;
    }
    queue->head = 0;
    queue->tail = 0;
    queue->capacity = size;
    return queue;
}
复制代码

这里create_queue 传入的参数size是数组的大小，即队列的大小。刚开始时，队列的头head和尾tail都指向数组的第0个位置。

其次，我们需要入队列操作:

// 入队列
int enqueue(array_queue *queue, int data) {
    // 如果queue为NULL，或者队列满时，返回-1
    if ((queue == NULL) || (queue->tail == queue->capacity)) {
        return ERR;
    }
    queue->data[queue->tail++] = data;
    return OK; 
}
复制代码

这里首先对队列作了判断:如果队列满了，则直接返回失败。否则将数据添加在下标为tail的位置，并且tail++。

最后还需要出队操作:

// 出队列
int dequeue(array_queue *queue, int *data) {
    // 没有数据时，出队列返回错误
    if ((queue == NULL) || (data == NULL) || (queue->head == queue->tail)) {
        return ERR;
    }
    (*data) = queue->head;
    queue->head++;
    return OK;
}
复制代码

这里，dequeue有两个参数，其中, data是一个出参，用来存储出队列的数据。出队操作也是先做一个判断:如果队列为空，则直接返回失败。否则，将队头传给data，并且队头++。
完整的代码可以见 附录1。

1.1 改进

上面的代码实现其实有一个问题：随着不停的进行入队和出队的操作，head和tail都会往后移动。当tail移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。这样会极大的浪费内存。为了解决这个问题，需要进行数据搬移，当tail到最后的时候，当再次有数据入队时，如果还有空闲空间，则进行一次数据的搬移操作。所以，对于出队函数保持不变，需要改造一下入队函数的实现。具体代码如下:

// 入队列
int enqueue(array_queue *queue, int data) {
    // 队列为空，或者队列满时，返回-1
    if (queue == NULL) {
        return ERR;
    }

    if (queue->tail == queue->size) {
        // 如果head为0，说明确实是满了
        if (queue->head == 0) {
            return ERR;
        }
        int i;
        int baseIndex = queue->head;
        for (i = queue->head; i < queue->tail; i++) {
            queue->data[i - baseIndex];
        }
        queue->tail -= baseIndex;
        queue->head = 0;
    }
    queue->data[queue->tail++] = data;
    return OK; 
}
复制代码

2. 循环队列

上面基于数组的队列的实现中，当tail == capacity时，需要数据搬移，这样会导致入队的操作性能降低。为了避免数据搬移，可以用循环队列。

关于循环队列需要理解以下内容:

  1. 循环队列入队的伪算法
  • 把值存在tail所在的位置
  • tail = (tail + 1) % capacity
  1. 循环队列出队的伪算法：
  • 先保存出队的值
  • head = (head + 1) % capacity
  1. 判断循环队列是否为空
  • head == tail
  1. 判断循环队列是否为满

队列满时的循环队列.png

如图所示，假如数组的大小是7，并且队列中此时已经放入数据1,2,3,4,5,6了。如果再放一个数据，则此时head == tail了，这跟上面判断循环队列是否为空的条件是一样的。没法区分到底是队列为空，还是队列满了的。所以为了区分，我们最后一个存储空间不用。所以判断循环队列是否为满的条件是:
(tail + 1) % capacity == head。
此时循环队列的tail其实是没有存储数据的。所以会浪费一个数组的存储空间。

至于为啥这里要对capacity取余，是因为假如现在tail = capacity -1，而head = 0。则 tail + 1 = capacity。而head = 0，所以用 (tail + 1) % capacity = capacity % capacity = 0。完整的代码实现可以见 附录2。

当然，上面只是一种方法来判断循环链表是否为空。这里还有另外一种方法:额外定义一个当前数组大小的值size。这样队列满的条件就是”当前队列的大小 等于 数组的大小”了。这样数组最后一个空间也不会浪费了。而且也更容易理解。(当然这里数据类型是int型，我多了个int 型的参数size，和上面不用最后一个空间，其实是一样的。但是当数据类型不是int型，而是大小比int型大时, 下面的这种实现更省内存。)

typedef struct {
    int capacity; // 队列数组的容量
    int size; // 当前队列数组的大小
    int head; // 队头的位置
    int tail; // 队尾的下一个位置
    int *data; // 数组
} MyCircularQueue;
复制代码

具体实现可以参考附录3。

3. 用链表实现队列

用链表实现的队列就不存在队列满的情况了。用链表实现的队列的数据结构如下。这里还是需要两个指针head和tail。head指向链表的第一个结点，tail指向链表的最后一个结点。当要入队时，tail->next = new_node, tail = tail->next。出队时, head = head->next。
具体实现可以见 附录4。

typedef struct tagQueue_node {
    int data;
    struct tagQueue_node *next; 
} queue_node;

typedef struct tagList_queue {
    int num; // 当前元素的个数
    queue_node *head;
    queue_node *tail;
} list_queue;
复制代码

4. Golang中的channel

了解Go语言的同学应该知道在Go语言中，channel(通道)是Golang在语言层面上提供的goroutine间的通信方式，你去读源码就会发现，channel底层的数据结构就用到了队列。
这里给出两篇博客，剖析了channel的底层数据结构。推荐大家看看:

  1. 《Go专家编程》Go channel实现原理剖析

  2. 图解Go的channel底层原理

5. 参考文献

  1. blog.csdn.net/lpp09003201…
  2. time.geekbang.org/column/arti…

附录1:队列的数组C语言实现

数组实现队列的C语言实现完整代码:

// array_queue.h头文件相关代码
#ifndef ARRAY_QUEUE_H
#define ARRAY_QUEUE_H

#define OK 0
#define ERR 1

typedef struct tagarray_queue {
    int capacity; // 队列的大小
    int head; // 队头的位置
    int tail; // 队尾的下一个位置
    int *data; // 数据存储区
} array_queue;
#endif


// array_queue.c 相关代码
#include <stdlib.h>
#include <stdio.h>
#include "array_queue.h"

array_queue *create_queue(int size) {
    if (size <= 0) {
        return NULL;
    }
    array_queue *queue = (array_queue *)malloc(sizeof(array_queue));
    if (queue == NULL) {
        return NULL;
    }
    queue->data = (int *)malloc(size * sizeof(int));
    if (queue->data == NULL) {
        free(queue);
        queue = NULL;
        return NULL;
    }
    queue->head = 0;
    queue->tail = 0;
    queue->capacity = size;
    return queue;
}

// 入队列
int enqueue(array_queue *queue, int data) {
    // 队列为空，或者队列满时，返回-1
    if ((queue == NULL) || (queue->tail == queue->capacity)) {
        return ERR;
    }
    queue->data[queue->tail++] = data;
    return OK; 
}

// 出队列
int dequeue(array_queue *queue, int *data) {
    // 没有数据时，出队列返回错误
    if ((queue == NULL) || (data == NULL) || (queue->head == queue->tail)) {
        return ERR;
    }
    (*data) = queue->head;
    queue->head++;
    return OK;
}

// 销毁队列
void destory_queue(array_queue *queue) {
    if (queue == NULL) {
        return;
    }
    if (queue->data != NULL) {
        free(queue->data);
        queue->data = NULL;
    }
    free(queue);
    return;
}

// 打印队列
void print_queue(array_queue *queue) {
    printf("\n\n");
    if (queue == NULL) {
        printf("\nqueue is NULL.");
        return;
    }
    printf("\n size:%d,head:%d, tail:%d.",
        queue->capacity, queue->head, queue->tail);
    
    int i;
    for (i = queue->head; i < queue->tail; i++) {
        printf("\n\t array[%d]:%d",i, queue->data[i]);
    }
    return;
}

int main() {
    int size = 4;
    array_queue *queue = create_queue(size);
    if (queue == NULL) {
        printf("\n queue create fail.");
        return ERR;
    }

    // 队列为空时，出队列返回错误
    int data = 0;
    int ret = dequeue(queue, &data);
    if (ret != OK) {
        printf("\n dequeue failed.");
    }

    int i;
    // 队列大小是4，入队5个
    for (i = 0; i < size + 1; i++) {
        ret = enqueue(queue, i);
        if (ret != OK) {
            printf("\n queue %d enqueue failed.", i);
        }
    }

    // 打印队列
    print_queue(queue);

    ret = dequeue(queue, &data);
    if (ret != OK) {
        printf("\n dequeue failed.");
    }
    print_queue(queue);

    ret = dequeue(queue, &data);
    if (ret != OK) {
        printf("\n dequeue failed.");
    }
    print_queue(queue);

    ret = dequeue(queue, &data);
    if (ret != OK) {
        printf("\n dequeue failed.");
    }
    print_queue(queue);

    ret = dequeue(queue, &data);
    if (ret != OK) {
        printf("\n dequeue failed.");
    }
    print_queue(queue);

    ret = enqueue(queue, 9);
    if (ret != OK) {
        printf("\n queue 9 enqueue failed.");
    }
    print_queue(queue);

    
    ret = enqueue(queue, 10);
    if (ret != OK) {
        printf("\n queue 10 enqueue failed.");
    }
    print_queue(queue);
    destory_queue(queue);
    return OK;
}
复制代码

附录2:循环队列的C语言实现

循环队列的实现:

int enqueue(array_queue *queue, int data) {
    // 队列为空，或者队列满时，返回-1
    if (queue == NULL) {
        return ERR;
    }
    if ((queue->tail + 1) % queue->capacity == queue->head) {
        printf("\ntail:%d, capacity:%d, head:%d", queue->tail, queue->capacity, queue->head);
        return ERR;
    }
    queue->data[queue->tail] = data;
    queue->tail = (queue->tail + 1) % queue->capacity;
    return OK; 
}

int dequeue(array_queue *queue, int *data) {
    // 没有数据时，出队列返回错误
    if ((queue == NULL) || (data == NULL) || (queue->head == queue->tail)) {
        return ERR;
    }
    (*data) = queue->head;
    queue->head = (queue->head + 1) % queue->capacity;
    return OK;
}

// 打印队列
void print_queue(array_queue *queue) {
    printf("\n\n");
    if (queue == NULL) {
        printf("\nqueue is NULL.");
        return;
    }
    printf("\n capacity:%d,head:%d, tail:%d.",
        queue->capacity, queue->head, queue->tail);
    
    int i;
    if (queue->head < queue->tail) {

        for (i = queue->head; i < queue->tail; i++) {
            printf("\n\t array[%d]:%d",i, queue->data[i]);
        }
    } else {
        for (i = queue->head; i < queue->capacity; i++) {
            printf("\n\t array[%d]:%d",i, queue->data[i]);
        }
        for (i = 0; i < queue->tail; i++) {
            printf("\n\t array[%d]:%d",i, queue->data[i]);
        }
    }
    return;
}
复制代码

附录3:带长度的循环队列的C语言实现

大家可以先在LeetCode上自己实现一遍:

设计循环队列

typedef struct {
    int capacity; // 队列数组的容量
    int size; // 当前队列数组的大小
    int head; // 队头的位置
    int tail; // 队尾的下一个位置
    int *data; // 数组
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue *queue = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    if (queue == NULL) {
        return NULL;
    }
    queue->size = 0;
    queue->head = 0;
    queue->tail = 0;
    queue->capacity = k;
    queue->data = (int *)malloc(sizeof(int) * k);
    return queue;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (obj->size == obj->capacity) {
        return false;
    }
    obj->data[obj->tail] = value;
    obj->tail = (obj->tail + 1) % (obj->capacity); // 这里取余是为了当tail == capacity - 1时, tail + 1 = capacity，取余后 tail = 0
    obj->size++;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (obj->size == 0) {
        return false;
    }
    obj->head = (obj->head + 1) % (obj->capacity);
    obj->size--;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (obj->size == 0) {
        return -1;
    }
    return obj->data[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (obj->size == 0) {
        return -1;
    }
    return obj->data[(obj->tail - 1 + obj->capacity) % (obj->capacity)];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return (obj->size == 0) ? true :false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->size == obj->capacity) ? true : false;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    if (obj == NULL) {
        return;
    }
    free(obj->data);
    obj->data = NULL;
    free(obj);
    return;
}
复制代码

附录4: 队列的链表C语言实现

链表实现队列完整代码:

// list_queue.h
#ifndef LIST_QUEUE_H
#define LIST_QUEUE_H

#define OK 0
#define ERR 1
typedef struct tagQueue_node {
    int data;
    struct tagQueue_node *next; 
} queue_node;

typedef struct tagList_queue {
    int num; // 当前元素的个数
    queue_node *head;
    queue_node *tail;
} list_queue;
#endif


// list_queue.c
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "list_queue.h"
#include <pthread.h>

// 判断队列是否为空
bool list_queue_is_empty(list_queue *queue)
{
    return queue->num == 0;
}

// 创建队列
list_queue *list_queue_create()
{
    list_queue *queue = (list_queue *)malloc(sizeof(list_queue));
    if (queue == NULL) {
        return NULL;
    }

    queue->num = 0;
    queue->head = NULL;
    queue->tail = NULL;
    return queue;
}

// 入队列
int list_queue_enqueue(list_queue *queue, int data)
{
    if (queue == NULL) {
        printf("enqueue fail, queue is NUll.\n");
        return ERR;
    }

    queue_node *tmp = (queue_node *)malloc(sizeof(queue_node));
    if (tmp == NULL) {
        printf("enqueue fail, malloc queue_node fail.\n");
        return ERR;
    }
    tmp->data = data;
    tmp->next = NULL;
    if (queue->head == NULL) {
        queue->head = tmp;
    } else {
        queue->tail->next = tmp;
    }
    queue->tail = tmp;
    queue->num++;
    return OK;
}

// 出队列
int list_queue_dequeue(list_queue *queue, int *data)
{
    if (queue == NULL) {
        printf("dequeue fail. queue is NULL.\n");
        return ERR;
    }
    if (list_queue_is_empty(queue)) {
        printf("dequeue fail. queue is empty.\n");
        return ERR;
    }
    queue_node *tmp = queue->head;
    (*data) = queue->head->data;
    queue->head = queue->head->next;
    queue->num--;
    if (queue->head == NULL) {
        queue->tail = NULL;
    }
    free(tmp);
    return OK;
}

// 销毁队列
void list_queue_destory(list_queue *queue)
{
    if (queue == NULL) {
        return;
    }

    int data = 0;
    while (!list_queue_is_empty(queue)) {
        (void)list_queue_dequeue(queue, &data);
    }

    free(queue);
    return;
}

// 打印队列
void list_queue_print(list_queue *queue)
{
    if (queue == NULL) {
        return;
    }
    printf("print queue: num:%d: ", queue->num);
    queue_node *tmp = queue->head;
    while (tmp != NULL) {
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }
    printf("\n\n");
    return; 
}

int main() {
    list_queue *queue = list_queue_create();
    if (queue == NULL) {
        return ERR;
    }
    int i;
    int num = 6;
    int data = 0;
    for (i = 0; i < num; i++) {
        (void)list_queue_enqueue(queue, i);
    }
    list_queue_print(queue);

    int ret = list_queue_dequeue(queue, &data);
    if (ret != OK) {
        return ret;
    }
    printf("dequeue number is %d.\n", data);
    list_queue_print(queue);

    ret = list_queue_dequeue(queue, &data);
    if (ret != OK) {
        return ret;
    }
    printf("dequeue number is %d.\n", data);
    list_queue_print(queue);

    list_queue_destory(queue);
    return OK;
}
复制代码
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
后端
喜欢就支持一下吧
点赞0 分享
AI-robot的头像-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
14年前 2.6W+
机器学习之随机森林回归篇（RandomForestRegressor）-一一网
机器学习之随机森林回归篇（RandomForestRegressor）
机器学习之随机森林回归篇（RandomForestRegressor）
4年前 4203
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS-一一网
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
4年前 3895
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞-一一网
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
19年前 3842
Wireshark之抓包文件保存-一一网
Wireshark之抓包文件保存
Wireshark之抓包文件保存
4年前 3406
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3135
相关推荐
Wireshark之抓包文件保存-一一网
Wireshark之抓包文件保存
Wireshark之抓包文件保存
4年前 3406
Integer的最大值是什么？｜ Java Debug 笔记-一一网
Integer的最大值是什么？｜ Java Debug 笔记
Integer的最大值是什么？｜ Java Debug 笔记
4年前 2767
使用arthas trace命令查看代码各方法响应时间-一一网
使用arthas trace命令查看代码各方法响应时间
使用arthas trace命令查看代码各方法响应时间
4年前 2723
Spring Boot集成Druid异常discard long time none received connection.-一一网
Spring Boot集成Druid异常discard long time none received connection.
Spring Boot集成Druid异常discard long time none received connection.
4年前 2137
pandas系列之导出为.csv文件-一一网
pandas系列之导出为.csv文件
pandas系列之导出为.csv文件
4年前 2109
使用XXL-JOB时，如何避免多台服务器重复调度任务？｜工作踩坑系列-一一网
使用XXL-JOB时，如何避免多台服务器重复调度任务？｜工作踩坑系列
使用XXL-JOB时，如何避免多台服务器重复调度任务？｜工作踩坑系列
4年前 1681
搜索
开启精彩搜索
世界，您好！-一一网
3.7W+人已阅读
世界，您好！
TOP1
番茄社区无限观看+付费视频破解教程-一一网
番茄社区无限观看+付费视频破解教程
5年前3.2W+人已阅读
TOP2
香蕉视频v3.8.3_VIP会员破解教程-一一网
香蕉视频v3.8.3_VIP会员破解教程
5年前3.1W+人已阅读
TOP3
[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网
密码保护：[桜井宁宁]COS和泉纱雾超可爱写真福利集
5年前2.8W+人已阅读
TOP4
[桜井宁宁] 爆乳奶牛少女cos写真-一一网
密码保护：[桜井宁宁] 爆乳奶牛少女cos写真
5年前2.8W+人已阅读
TOP5
快猫v1.1.7会员破解版_最新快猫vip破解教程大全-一一网
快猫v1.1.7会员破解版_最新快猫vip破解教程大全
5年前2.7W+人已阅读
TOP6
标签云
默认路由黑裙黑群晖麦克风车机鸿蒙系统鸿蒙系统鸿蒙OS鸿蒙驱动软件驱动题库音频剪辑音乐剪辑面板面具静态雷石集群随机阿里云