AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

队列的实现

2023-09-14 212
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 队列的实现

@[toc]

本篇文章将讲解队列。

队列的定义

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

可以将队列类比成日常生活中的排队，比如食堂派对打饭，银行排队处理业务等。
比如下图的队列：
在这里插入图片描述
队列只允许从队尾(rear)插入，从队头(front)删除，所以对于队列结构，先插入的元素总是先被删除。

队列的抽象数据类型定义

定义如下：

ADT Queue{
   
   
    数据对象：D = {
   
   ai|ai∈ElemSet,i = 1,2,...,n-1,n,n>=0}
    数据关系：R = {
   
   <ai-1,ai>|ai-1,ai∈D,i=2,3,...,n-1,n}
    基本操作：
        InitQueue(&Q);//初始化对了
        DestroyQueue(&Q);//销毁队列
        ClearQueue(&Q);//清空队列
        QueueLength(Q);//求队列长度
        GetHead(Q,&val);//求队头元素
        EnQueue(&Q,val);//入队
        DeQueue(&Q,&val);//出队
        ......
}ADT Queue

队列的顺序实现

队列同样可以顺序实现和链式实现，分别称作：顺序队列和链式队列。
先来说说队列的顺序实现，可以通过数组实现，顺序队列的结构定义如下：

typedef struct {
   
   
    int *base;//初始化的动态分配存储空间
    int front;//头指针
    int rear;//尾指针
}Queue,*PQueue;

注意这里的头指针和尾指针并不是真正的指针，它只是数组的下标，起一个类似于指针的作用而已。

初始情况下，队列为空该如何表示呢？
队列由数组实现，所以数组为空即为队列空，我们将头指针和尾指针都置为0，即表示空队列。

顺序队列的基本操作

入队

假设如下的一个队列：
在这里插入图片描述
如何实现入队操作呢？
将元素放入队尾下标的位置，然后让队尾下标加1，即：base[rear] = val;rear++。
在这里插入图片描述
此时队列已满，尾指针rear的值为5，所以判断队列是否满，就看队尾指针rear的值是否等于数组的最大容量，即：rear == MAXSIZE。

出队

继续看这个队列：
在这里插入图片描述
如何实现出队呢？
取出队头下标对应的元素值，然后队头指针加1，即：val = base[front];front++。
在这里插入图片描述
我们继续将队列元素出队，直到最后一个元素也出队，此时队头指针和队尾指针相等：
在这里插入图片描述
所以，判断队列是否空的条件为：rear == front。

普通顺序队列的缺陷

不过通常我们都不会使用这样的队列来解决实际问题，为什么呢？我们来看看它的缺陷。
假设有下面的一个队列：
在这里插入图片描述
该队列是如何形成的呢？首先有一个空队列，然后执行入队操作，直到队满，此时尾指针rear的值为5；然后执行三次出队操作，状态就如上图。

试想一下，现在还能执行入队操作吗？
在入队操作执行之前，我们首先要判断队列是否满，如果满，则无法入队。
队列是否满的条件是rear == MAXSIZE，很显然，这里表示队满了。但实际上，队列满了吗？当然没满，下面还有三个空闲位置呢。

所以，普通队列存在着一个溢出的问题。
若头指针front == 0，而尾指针rear == MAXSIZE，此时表示队列真的满了，这时候入队是真溢出。
若头指针front≠0，而尾指针rear == MAXSIZE，此时队列并没有真的满，这时候后入队是假溢出。

循环队列

为了解决假溢出的问题，我们可以将普通的队列改造成循环队列。
我们可以让队列中的空间循环使用，比如下面的情况：
在这里插入图片描述
此时判断该队列是满的，如何循环利用起下面的空间呢？
当rear的值为MAXSIZE的时候，我们可以将rear的值赋值为0，使尾指针rear重新指回到数组开头，如果rear所指的位置是空着的，就可以继续使用了；头指针front也是如此。

因为队头和队尾指针可以循环移动，所以空循环队列和满循环队列的判断条件就无法确定了，为此，我们可以牺牲队列中的一个空间，来区分队满和队空。比如下面的情况：
在这里插入图片描述
少用一个空间，而此时判断队列是否满的情况就是(rear + 1) % MAXSIZE == front。

循环顺序队列的基本操作

下面介绍循环队列的一些基本操作。

顺序队列的初始化

初始化操作就是开辟一段数组内存，然后将队头和队尾指针置为0。

Queue InitQueue(){
   
   
    Queue q;
    //分配数组内存
    q.base = (int*) malloc(sizeof(int) * MAXSIZE);
    if(q.base == NULL){
   
   
        exit(-1);
    }
    q.front = q.rear = 0;
    return q;
}

求顺序队列的长度

普通的队列求长度只需要用队尾指针减去队头指针即可，但是循环队列的指针可以随意指向，所以很可能出现相减得负数的情况，为此，我们需要对结果进行一定的处理：

int QueueLength(Queue q){
   
   
    return (q.rear - q.front + MAXSIZE) % MAXSIZE;
}

顺序队列的入队操作

循环队列的入队操作和普通队列没有什么区别，区别在于要针对队尾指针做循环处理。

int EnQueue(PQueue q,int val){
   
   
    //判断队列是否满
    if((q->rear + 1) % MAXSIZE == q->front){
   
   
        return -1;
    }
    q->base[q->rear] = val;
    q->rear = (q->rear + 1) % MAXSIZE;
    return 1;//入队成功，返回1
}

这里巧妙地使用取模操作，使尾指针rear在0到MAXSIZE之间循环。

顺序队列的出队操作

出队操作就没有什么说的了，细节都已经讲明白了。

int OnQueue(PQueue q,int *val){
   
   
    //判断队列是否空
    if(q->front == q->rear){
   
   
        return -1;
    }
    *val = q->base[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    return 1;//出队成功，返回1
}

取顺序队列的队头元素

取队头元素很简单， 直接输出队头指针对应的元素值即可：

int GetHead(Queue q){
   
   
    //判断队列是否空
    if(q.front == q.rear){
   
   
        return -1;
    }
    return q.base[q.front];
}

队列的链式实现

和其它数据结构一样，顺序队列的缺点是存储容量不灵活，所以如果对存储容量有要求，就需要使用链式队列。
下面是链式队列的结构定义：

//结点
typedef struct Node{
   
   
    int data;
    struct Node *next;
}Node,*PNode;

//队列
typedef struct {
   
   
    PNode front;//头指针
    PNode rear;//尾指针
}Queue,*PQueue;

链式队列的基本操作

下面介绍链式队列的一些基本操作。

链式队列的初始化

void InitQueue(PQueue q){
   
   
    //初始队头和队尾指针均指向头结点
    q->front = q->rear = (PNode) malloc(sizeof(Node));
    if(q->front == NULL || q->rear == NULL){
   
   
        exit(-1);
    }
    q->front->next = NULL;//队头结点指针域置为NULL
}

链式队列的初始化也非常简单，首先开辟一个空间作为头结点，然后让队头队尾指针均指向头结点，最后让队头结点指针域赋值为NUULL。

链式队列的销毁

void DestroyQueue(PQueue q){
   
   
    PNode p;
    //当前结点是否为空
    while(q->front != NULL){
   
   
        //保存当前结点
        p = q->front->next;
        free(p);//释放内存
        q->front = p;
    }
}

链式队列的入队操作

void EnQueue(PQueue q,int val){
   
   
    //创建新结点
    PNode p = (PNode) malloc(sizeof(Node));
    if(p == NULL){
   
   
        exit(-1);
    }
    p->data = val;
    p->next = NULL;//队尾结点指针域为NULL
    q->rear->next = p;//将队尾结点指向新结点
    q->rear = p;//队尾指针为新结点
}

在队尾插入结点。

链式队列的出队操作

int OnQueue(PQueue q,int *val){
   
   
    PNode p;
    //判断队列是否空
    if(q->front == q->rear){
   
   
        return -1;
    }
    p = q->front->next;
    *val = p->data;
    q->front->next = p->next;
    if(q->rear == p){
   
   
        q->rear = q->front;
    }
    free(p);
    return 1;//出队成功，返回1
}

在队头删除结点。

这些操作都非常简单，就不一一分析了，会发现，有链表的基本，再来学习这些东西会非常简单。

源代码

顺序队列代码

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define MAXSIZE 10

typedef struct {
   
   
    int *base;//初始化的动态分配存储空间
    int front;//头指针
    int rear;//尾指针
}Queue,*PQueue;

int GetHead(Queue q){
   
   
    //判断队列是否空
    if(q.front == q.rear){
   
   
        return -1;
    }
    return q.base[q.front];
}

int EnQueue(PQueue q,int val){
   
   
    //判断队列是否满
    if((q->rear + 1) % MAXSIZE == q->front){
   
   
        return -1;
    }
    q->base[q->rear] = val;
    q->rear = (q->rear + 1) % MAXSIZE;
    return 1;//入队成功，返回1
}

int OnQueue(PQueue q,int *val){
   
   
    //判断队列是否空
    if(q->front == q->rear){
   
   
        return -1;
    }
    *val = q->base[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    return 1;//出队成功，返回1
}

int QueueLength(Queue q){
   
   
    return (q.rear - q.front + MAXSIZE) % MAXSIZE;
}

Queue InitQueue(){
   
   
    Queue q;
    //分配数组内存
    q.base = (int*) malloc(sizeof(int) * MAXSIZE);
    if(q.base == NULL){
   
   
        exit(-1);
    }
    q.front = q.rear = 0;
    return q;
}

链式队列代码

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define MAXSIZE 10

//结点
typedef struct Node{
   
   
    int data;
    struct Node *next;
}Node,*PNode;

//队列
typedef struct {
   
   
    PNode front;//头指针
    PNode rear;//尾指针
}Queue,*PQueue;

int OnQueue(PQueue q,int *val){
   
   
    PNode p;
    //判断队列是否空
    if(q->front == q->rear){
   
   
        return -1;
    }
    p = q->front->next;
    *val = p->data;
    q->front->next = p->next;
    if(q->rear == p){
   
   
        q->rear = q->front;
    }
    free(p);
    return 1;//出队成功，返回1
}

void EnQueue(PQueue q,int val){
   
   
    //创建新结点
    PNode p = (PNode) malloc(sizeof(Node));
    if(p == NULL){
   
   
        exit(-1);
    }
    p->data = val;
    p->next = NULL;//队尾结点指针域为NULL
    q->rear->next = p;//将队尾结点指向新结点
    q->rear = p;//队尾指针为新结点
}

void DestroyQueue(PQueue q){
   
   
    PNode p;
    //当前结点是否为空
    while(q->front != NULL){
   
   
        //保存当前结点
        p = q->front->next;
        free(p);//释放内存
        q->front = p;
    }
}

void InitQueue(PQueue q){
   
   
    //初始队头和队尾指针均指向头结点
    q->front = q->rear = (PNode) malloc(sizeof(Node));
    if(q->front == NULL || q->rear == NULL){
   
   
        exit(-1);
    }
    q->front->next = NULL;//队头结点指针域置为NULL
}
文章标签：
前端开发
梳中分的坤坤
目录
相关文章
很久
|
机器学习/深度学习 存储 数据挖掘
Google Colab：云端的Python编程神器
Google Colab，全名Google Colaboratory，是Google Research团队开发的一款云端编程工具，它允许任何人通过浏览器编写和执行Python代码。Colab尤其适合机器学习、数据分析和教育目的。它是一种托管式Jupyter笔记本服务，用户无需设置，就可以直接使用，同时还能获得GPU等计算资源的免费使用权限。
很久
1362 0
Google Colab：云端的Python编程神器
苍天饶过谁？
|
存储 编解码 Cloud Native
FFmpeg修复受损视频
FFmpeg修复受损视频
苍天饶过谁？
802 0
水车306
|
关系型数据库 MySQL 数据安全/隐私保护
查看mysql 默认端口号和修改端口号
1. 登录mysql mysql -u root -p //输入密码 　　 2. 使用命令show global variables like 'port';查看端口号 mysql> show global variables like 'port'; 　　 3. 修改端口，编辑/etc/my.cnf文件，早期版本有可能是my.conf文件名，增加端口参数，并且设定端口，注意该端口未被使用，保存退出。
水车306
23338 0
游客yjdcmtrkvjoua
|
4月前
|
API 开发工具 开发者
API测评：快速获取门店客流趋势数据
本文介绍了一个门店客流趋势API，帮助创业者和开发者便捷获取门店客流数据。只需提供场景ID和查询时间段，即可获取详细客流分析数据，包括日均、总客流、外卖客流及竞品对比等，助力门店高效运营与决策分析。
游客yjdcmtrkvjoua
192 0
API测评：快速获取门店客流趋势数据
游客4aq4gohe3o5zk
|
移动开发 JavaScript API
Sprunki Game 实现技术分析及介绍
**Sprunki** 是一款基于音乐创作的游戏，作为经典游戏 **Incredibox** 的粉丝改版，它采用 HTML5 和 JavaScript 构建，通过拖拽式 UI 和模块化声音系统，提供了一个创意十足的音乐创作平台。游戏支持多种设备，并融入了 CSS3 动画和 Web Audio API，增强视觉与音效同步。玩家还可以通过社交媒体分享作品，参与社区互动。Sprunki 不仅是一款游戏，更是一个开放的创作平台。
游客4aq4gohe3o5zk
1361 2
Echo_Wish
|
6月前
|
传感器 机器学习/深度学习 人工智能
VR硬件进化史：从“晕3D”到沉浸式未来
VR硬件进化史：从“晕3D”到沉浸式未来
Echo_Wish
364 4
蓝易云
|
8月前
|
安全 开发工具 Android开发
【Android Git】Git版本回退方式
在实际操作中，选择合适的版本回退方式，可以有效地管理代码版本，提高开发效率和代码质量。
蓝易云
463 26
jsjsjjs
|
7月前
|
存储 安全 算法
鸿蒙NEXT如何保证应用安全：详解鸿蒙NEXT数字签名和证书机制
本文对鸿蒙NEXT公开资料进行了深入分析和解读，梳理了鸿蒙单框架应用的签名机制，拆解每一步的实操过程和背后的实现原理，并对源码分析整理签名的校验机制。从中管中窥豹，探究鸿蒙系统的安全设计思路，给从事鸿蒙研发的同学提供一些借鉴。
jsjsjjs
674 3
穿过生命散发芬芳
|
10月前
|
弹性计算 安全 数据库
活动实践 | 通过弹性公网 IP 确保服务迁移时公网 IP 不变
该方案通过弹性公网IP（EIP）实现公网IP与不同资源的灵活关联和解绑，支持业务水平扩容和资源迁移。具体步骤包括：创建ECS实例并分配固定公网IP，安装Web服务，创建自定义镜像以快速部署新实例，将原实例的固定公网IP转为EIP，并将其解绑后绑定到新实例上，确保服务迁移后对外IP不变。最后，清理资源以避免不必要的费用。
穿过生命散发芬芳
346 3
大树营养快线
|
存储 缓存 运维
一致性哈希算法的缺点是什么？
【10月更文挑战第25天】虽然一致性哈希算法具有一些优点，如在节点变化时数据迁移量相对较小等，但也存在数据倾斜、虚拟节点复杂、节点数量少性能受限、数据迁移代价以及哈希函数选择等多方面的缺点。在实际应用中，需要根据具体的业务场景和系统需求，综合考虑这些因素，采取相应的优化措施来克服其缺点，充分发挥一致性哈希算法的优势。
大树营养快线
390 2