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

队列的实现

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

@[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
}
文章标签：
前端开发
梳中分的坤坤
目录
相关文章
Augety&amp;
|
7月前
|
存储 消息中间件 前端开发
队列
队列
Augety&amp;
80 0
Paranoid
|
缓存
指令缓存队列
指令缓存队列
Paranoid
71 0
云水闲
|
7月前
|
存储 Java
Java循环队列
Java循环队列
云水闲
48 0
醋溜马桶圈
|
7月前
队列的实现
队列的实现
醋溜马桶圈
68 0
DyeDD
|
C++
c++ 队列
队列的数据结构
DyeDD
40 0
阿甘兄
12 队列
12 队列
阿甘兄
44 0
青春：一叶知秋
|
算法
队列的运用
队列的运用
青春：一叶知秋
43 0
是小刘同学啦
|
存储
队列的实现（下）
队列的实现（下）
是小刘同学啦
59 0
是小刘同学啦
|
机器学习/深度学习 存储 C语言
队列的实现（上）
队列的实现（上）
是小刘同学啦
72 0
游离111
|
存储
队列的使用
队列的使用
游离111
81 0