【数据结构】数组实现队列(详细版)

目录

队列的定义

普通顺序队列的劣势——与链队列相比 

顺序队列实现方法:

一、动态增长队列

 1、初始化队列

 2、元素入队

 3、判断队列是否为空

 4、元素出队

 5、获取队首元素

6、获取队尾元素

 7、获取队列元素个数

8、销毁队列

 总结:

动态增长队列完整测试代码:

二、固定长度队列 

1、与动态增长队列的差异

2、判断是否队满 

固定长度队列完整测试代码:


本节我们采用数组(顺序表)形式实现队列,学习单链表实现请点击下方链接:

队列—单链表实现(C语言版)-CSDN博客

为了减少数组初始长度过大对内存空间的浪费,本节我们采用动态内存管理,相关函数请的介绍点击下方链接:

动态内存函数(malloc,free,calloc,realloc)-CSDN博客

循环队列的实现:

循环队列(数组实现)-CSDN博客



 

队列的定义

队列是一种基本的数据结构,它是一种先进先出(First In First Out,FIFO)的线性结构队列只允许在表的一端进行插入,而在另一端进行删除操作。这就相当于把数据排成一排,先插入的排在前面,后插入的排在后面,之后进行删除操作时也只能从前面依次删除。这种数据结构一般用于需要按照先后顺序进行处理的问题,如模拟系统、计算机网络中的缓存、操作系统中的进程调度等。队列的基本操作包括入队(插入元素到队尾)出队(从队头删除元素),队列还有一个重要的特性就是队列的长度是动态变化的,随着入队和出队的操作进行不断变化。

 ​​

普通顺序队列的劣势——与链队列相比 

  1. 长度固定:普通数组队列的长度是固定的,一旦数组被分配,其长度无法改变。当队列元素数量超过数组长度时,需要进行数组的扩容操作,这会导致性能上的开销。

  2. 内存的浪费:因为普通数组队列的长度固定,可能会出现队列中存在空闲的位置,导致内存的浪费。

为了解决上述 问题1,我们在本节中对顺序表采取动态内存管理,在必要时更新数组的长度,以保证顺序队列的长度足够使用。

 (补充:问题2 的解决需要使用循环队列,本节内容先为大家介绍一般队列的实现,等同学们对队列有了充分的理解之后,我们下节再进行循环队列的学习。)


顺序队列实现方法:

一、我们首先定义一个数组,数组的头部为队首,尾部为队尾。每当插入一个元素时,就将元素放在队尾,当删除一个元素时,将队首的元素删除。当队列为空时,不能再删除元素。

二、我们采用双指针法时刻记录队列的队首和队尾:

  1. 定义一个固定大小的数组作为队列的存储空间,并定义两个指针front和rear分别指向队列的队首和队尾。

  2. 初始化队列时,将front和rear都设置为0,表示队列为空。

  3. 插入元素时,将元素放入rear指针指向的位置,并将rear指针后移一位。

  4. 删除元素时,将front指针后移一位。

  5. 判断队列是否为空,只需要判断front和rear是否相等即可。


一、动态增长队列

 1、初始化队列

初始化队列时,将front和rear都设置为0,表示队列为空。

typedef int DataType;

typedef struct Queue
{
    DataType* a; // 队列的数组
    int front, rear; // 队列的头部和尾部位置索引
    int size; // 队列中元素的数量
    int capacity; // 队列的容量
} Queue;

// 初始化队列
void InitQueue(Queue* q)
{
    q->a = NULL; // 数组指针初始化为NULL
    q->front = q->rear = 0; // 头部和尾部位置索引初始化为0
    q->size = q->capacity = 0; // 元素数量和容量都初始化为0
}

 2、元素入队

// 入队
void QueuePush(Queue* q, DataType x)
{
    assert(q); // 断言q不为NULL
    if (q->capacity == q->rear)
    {
        // 如果队列已满,进行扩容操作
        int new_capacity = q->capacity == 0 ? 10 : q->capacity * 2; // 扩容的大小为原容量的2倍
        DataType* temp = (DataType*)realloc(q->a, new_capacity * sizeof(DataType)); // 重新分配内存空间
        if (temp == NULL)
        {
            perror("realloc fail"); // 扩容失败,则输出错误信息
            exit(-1); // 退出程序
        }
        q->capacity = new_capacity; // 更新队列的容量
        q->a = temp; // 更新数组指针
    }
    q->a[q->rear++] = x; // 在尾部插入新元素,并更新尾部位置索引
    q->size++; // 元素数量加1
}

 3、判断队列是否为空

判断队列是否为空,只需要判断front和rear是否相等即可。

// 判断队列是否为空
bool QueueEmpty(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (q->front == q->rear)
    {
        return true; // 头部和尾部位置索引相等,队列为空
    }
    return false; // 队列不为空
}

 4、元素出队

 删除元素时,将front指针后移一位。

void QueuePop(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (!QueueEmpty(q))
    {
        q->front++; // 更新头部位置索引
        q->size--; // 元素数量减1
    }
    else
    {
        printf("队列已空,删除失败!\n"); // 队列为空,无法出队
    }
}

5、获取队首元素

// 获取队首元素
DataType QueueTop(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (!QueueEmpty(q))
    {
        return q->a[q->front]; // 返回队首元素的值
    }
    else
    {
        printf("队列已空,获取队头元素失败!\n"); // 队列为空,无法获取队首元素
        exit(-1); // 退出程序
    }
}

6、获取队尾元素

队尾指针q->rear在最后一个元素的下一位,所以我们返回队尾元素时需要返回队尾坐标的前一个坐标所指向的元素。

// 获取队尾元素
DataType QueueTail(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (!QueueEmpty(q))
    {
        return q->a[q->rear - 1]; // 返回队尾元素的值
    }
    else
    {
        printf("队列已空,获取队尾元素失败!\n"); // 队列为空,无法获取队尾元素
        exit(-1); // 退出程序
    }
}

7、获取队列元素个数

// 获取队列中元素的数量
int QueueSize(Queue* q)
{
    assert(q); // 断言q不为NULL
    return q->size; // 返回元素数量
}

8、销毁队列

// 销毁队列
void QueueDestory(Queue* q)
{
    assert(q); // 断言q不为NULL
    free(q->a); // 释放队列的数组空间
    q->a = NULL; // 数组指针置为NULL
}

总结:

 通过对顺序队列的学习我们可以明显看到顺序队列的缺点。当我们删除队首元素后由于队列只能从队尾进行增加元素的操作,所以front指针之前的空间不能再进行使用

如果是在队列长度是固定长度的情况下,当队尾指针rear到达最大时,队列已满,数组内已经没有空间进行插入操作,但由于此时front指针前可能还有空余空间,这时我们就造成了空间的浪费。

我们把这种现象称为“假溢出”现象。那么通过数组的循环队列或者链队列我们可以很好的解决此类现象。

下节我们将对如何用数组实现循环队列进行介绍:循环队列(数组实现)-CSDN博客

动态增长队列完整测试代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int DataType;

typedef struct Queue
{
    DataType* a; // 队列的数组
    int front, rear; // 队列的头部和尾部位置索引
    int size; // 队列中元素的数量
    int capacity; // 队列的容量
} Queue;

// 初始化队列
void InitQueue(Queue* q)
{
    q->a = NULL; // 数组指针初始化为NULL
    q->front = q->rear = 0; // 头部和尾部位置索引初始化为0
    q->size = q->capacity = 0; // 元素数量和容量都初始化为0
}

// 判断队列是否为空
bool QueueEmpty(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (q->front == q->rear)
    {
        return true; // 头部和尾部位置索引相等,队列为空
    }
    return false; // 队列不为空
}

// 入队
void QueuePush(Queue* q, DataType x)
{
    assert(q); // 断言q不为NULL
    if (q->capacity == q->rear)
    {
        // 如果队列已满,进行扩容操作
        int new_capacity = q->capacity == 0 ? 10 : q->capacity * 2; // 扩容的大小为原容量的2倍
        DataType* temp = (DataType*)realloc(q->a, new_capacity * sizeof(DataType)); // 重新分配内存空间
        if (temp == NULL)
        {
            perror("realloc fail"); // 扩容失败,则输出错误信息
            exit(-1); // 退出程序
        }
        q->capacity = new_capacity; // 更新队列的容量
        q->a = temp; // 更新数组指针
    }
    q->a[q->rear++] = x; // 在尾部插入新元素,并更新尾部位置索引
    q->size++; // 元素数量加1
}

// 出队
void QueuePop(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (!QueueEmpty(q))
    {
        q->front++; // 更新头部位置索引
        q->size--; // 元素数量减1
    }
    else
    {
        printf("队列已空,删除失败!\n"); // 队列为空,无法出队
    }
}

// 获取队首元素
DataType QueueTop(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (!QueueEmpty(q))
    {
        return q->a[q->front]; // 返回队首元素的值
    }
    else
    {
        printf("队列已空,获取队头元素失败!\n"); // 队列为空,无法获取队首元素
        exit(-1); // 退出程序
    }
}

// 获取队尾元素
DataType QueueTail(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (!QueueEmpty(q))
    {
        return q->a[q->rear - 1]; // 返回队尾元素的值
    }
    else
    {
        printf("队列已空,获取队尾元素失败!\n"); // 队列为空,无法获取队尾元素
        exit(-1); // 退出程序
    }
}

// 获取队列中元素的数量
int QueueSize(Queue* q)
{
    assert(q); // 断言q不为NULL
    return q->size; // 返回元素数量
}

// 销毁队列
void QueueDestory(Queue* q)
{
    assert(q); // 断言q不为NULL
    free(q->a); // 释放队列的数组空间
    q->a = NULL; // 数组指针置为NULL
}

int main()
{
	Queue q;
	InitQueue(&q);
	QueuePush(&q, 5);
	QueuePush(&q, 6);
	QueuePush(&q, 7);
	QueuePush(&q, 8);
	QueuePush(&q, 9);
	QueuePush(&q, 10);
	DataType x;
	x = QueueTop(&q);
	printf("%d\n", x);
	x = QueueTail(&q);
	printf("%d\n", x);
	QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);
	x = QueueTop(&q);
	printf("%d\n", x);
    x = QueueSize(&q);
    printf("%d\n", x);
    QueueDestory(&q);
    return 0;
}

二、固定长度队列 

1、与动态增长队列的差异

由于固定长度队列无需扩容,所以不需要进行动态内存的分配,也不需要进行销毁队列的操作

同时相对于动态增长的队列,固定长度的队列需要判断队内元素数量是否达到了队列的最大容量。由于我们在代码中是先对队尾指针rear指向的位置添加元素,再对rear进行自增,更新队尾索引,所以在本代码中队满的判断条件是rear==MAXLEN


2、判断是否队满 

当对固定长度队列添加元素时,如果当前队列队尾指针已达到数组长度,由于队列只能从队尾添加元素,此时我们不能再为队列添加新的元素。所以在我们为队尾添加元素时,我们首先要判断队列是否已满——即队尾指针是否达到数组容量的最大值。

//判断队列是否为满
bool QueueFull(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (q->rear == MAXLEN)
    {
        return true; // 尾部位置达到数组长度最大值,队列为满
    }
    return false; // 队列不为满
}

明白了以上几点,我们对动态增长队列的代码稍作修改,添加判断队列是否已满的函数并对增加队列元素作出限制,就可得到固定长度队列的代码。

固定长度队列完整测试代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

#define MAXLEN 10
typedef int DataType;

typedef struct Queue
{
    DataType a[MAXLEN]; // 队列的数组
    int front, rear; // 队列的头部和尾部位置索引
    int size; // 队列中元素的数量
} Queue;

// 初始化队列
void InitQueue(Queue* q)
{
    assert(q);
    q->front = q->rear = 0; // 头部和尾部位置索引初始化为0
    q->size = 0; // 元素数量初始化为0
}

// 判断队列是否为空
bool QueueEmpty(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (q->front == q->rear)
    {
        return true; // 头部和尾部位置索引相等,队列为空
    }
    return false; // 队列不为空
}

//判断队列是否为满
bool QueueFull(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (q->rear == MAXLEN)
    {
        return true; // 尾部位置达到数组长度最大值,队列为满
    }
    return false; // 队列不为满
}

// 入队
void QueuePush(Queue* q, DataType x)
{
    assert(q); // 断言q不为NULL
    if (!QueueFull(q))//判断队列是否为满
    {
        q->a[q->rear++] = x; // 在尾部插入新元素,并更新尾部位置索引
        q->size++; // 元素数量加1
    }
    else
    {
        printf("队列已满\n");
        exit(-1);
    }
}

// 出队
void QueuePop(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (!QueueEmpty(q))
    {
        q->front++; // 更新头部位置索引
        q->size--; // 元素数量减1
    }
    else
    {
        printf("队列已空,删除失败!\n"); // 队列为空,无法出队
    }
}

// 获取队首元素
DataType QueueTop(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (!QueueEmpty(q))
    {
        return q->a[q->front]; // 返回队首元素的值
    }
    else
    {
        printf("队列已空,获取队头元素失败!\n"); // 队列为空,无法获取队首元素
        exit(-1); // 退出程序
    }
}

// 获取队尾元素
DataType QueueTail(Queue* q)
{
    assert(q); // 断言q不为NULL
    if (!QueueEmpty(q))
    {
        return q->a[q->rear - 1]; // 返回队尾元素的值
    }
    else
    {
        printf("队列已空,获取队尾元素失败!\n"); // 队列为空,无法获取队尾元素
        exit(-1); // 退出程序
    }
}

// 获取队列中元素的数量
int QueueSize(Queue* q)
{
    assert(q); // 断言q不为NULL
    return q->size; // 返回元素数量
}


int main()
{
    Queue q;
    InitQueue(&q);
    QueuePush(&q, 5);
    QueuePush(&q, 6);
    QueuePush(&q, 7);
    QueuePush(&q, 8);
    QueuePush(&q, 9);
    QueuePush(&q, 10);
    QueuePush(&q, 5);
    QueuePush(&q, 6);
    QueuePush(&q, 7);
    QueuePush(&q, 8);
    //QueuePush(&q, 9);
    //QueuePush(&q, 10);
    DataType x;
    x = QueueTop(&q);
    printf("%d\n", x);
    x = QueueTail(&q);
    printf("%d\n", x);
    QueuePop(&q);
    QueuePop(&q);
    QueuePop(&q);
    QueuePop(&q);
    QueuePop(&q);
    x = QueueTop(&q);
    printf("%d\n", x);
    x = QueueSize(&q);
    printf("%d\n", x);
    return 0;
}

如果有同学在部分地方有疑惑,欢迎评论区讨论。

本节内容告一段落,我们下节博客见。

循环队列(数组实现)-CSDN博客

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/290257.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

配网故障定位技术的研究与实现:提高配网运行效率的必要手段

随着电力系统的不断发展&#xff0c;配电网作为电力系统的重要组成部分&#xff0c;其安全性和稳定性对于整个电力系统的运行具有重要意义。然而&#xff0c;配电网在运行过程中&#xff0c;由于各种原因导致的故障事件时有发生&#xff0c;严重影响了配网的运行效率和供电质量…

【单片机 TB作品】节拍器,电子音乐节拍器,51单片机,Proteus仿真

节拍器的使用可以使练琴者正确掌握乐曲的速度,从而使音 乐练习达到事半功倍的效果。本课题基于单片机设计具有声光晋 示的电子乐器节拍器,充分利用单片机的定时和中断系统,通过 C语言程序设计,控制外部相关硬件电路,实现对音乐速,度 40~120次/分钟范围内连续可调,节拍114、 2/4…

解决sublime中文符号乱码问题

效果图 原来 后来 问题不是出自encode文件编码&#xff0c;而是win10的字体问题。 解决方法 配置&#xff1a; { "font_face":"Microsoft Yahei", "dpi_scale": 1.0 } 参考自 Sublime 输入中文显示方框问号乱码_sublime中文问号-CSDN博…

学习调整echarts中toolbox位置toolBox工具栏属性

学习调整echarts中toolbox位置toolBox工具栏属性 toolbox工具栏属性介绍示例代码代码参数说明 toolbox工具栏属性介绍 参考网址&#xff1a;https://echarts.apache.org/zh/option.html#tooltip 属性类型说明toolbox.showbooleanboolean 默认值为true&#xff0c;是否显示工具…

Matlab进阶绘图第37期—多色悬浮柱状图

多色悬浮柱状图是一种特殊的柱状图。 与常规柱状图相比&#xff0c;多色悬浮柱状图可以通过悬浮的矩形展示最小值到最大值的范围&#xff08;或其他范围表达&#xff09;&#xff0c;并通过颜色进行美化/区分/附加信息。 本文使用自己制作的Floatingbar小工具进行多色悬浮柱状…

Oracle database 12cRAC异地恢复至单机

环境 rac 环境 byoradbrac Oracle12.1.0.2 系统版本&#xff1a;Red Hat Enterprise Linux Server release 6.5 软件版本&#xff1a;Oracle Database 12c Enterprise Edition Release 12.1.0.2.0 - 64bit byoradb1&#xff1a;172.17.38.44 byoradb2&#xff1a;172.17.38.4…

Kotlin采集美团商家信息 同行竞争价格监控

“南方小土豆”挤爆哈尔滨旅游市场&#xff0c;一个冬天让哈尔滨火出了圈&#xff0c;让全国观众看见了不一样的逆向旅游热&#xff0c;虽说我心驰神往&#xff0c;但是无奈加班敲代码&#xff0c;连休息的时间都没有。前段时间我通过用java写了一个美团爬虫程序&#xff0c;今…

智慧工厂:科技与制造融合创新之路

随着科技的迅猛发展&#xff0c;智慧工厂成为制造业领域的热门话题。智慧工厂利用先进的技术和智能化系统&#xff0c;以提高生产效率、降低成本、增强产品质量和灵活性为目标&#xff0c;正在引领着未来制造业的发展。 智慧工厂的核心是数字化和自动化生产&#xff0c;相较于传…

Spark基础解析(一)

1、 Spark概述 1.1 什么是Spark 1.2Spark内置模块 Spark Core&#xff1a;实现了Spark的基本功能&#xff0c;包含任务调度、内存管理、错误恢复、与存储系统交互等模块。Spark Core中还包含了对弹性分布式数据集(Resilient Distributed DataSet&#xff0c;简称RDD)的API定义…

基于SSM的校园快递管理系统

目录 前言 开发环境以及工具 项目功能介绍 学生&#xff1a; 管理员&#xff1a; 详细设计 获取源码 前言 本项目是一个基于IDEA和Java语言开发的基于SSM的校园快递管理系统应用。应用包含学生端和管理员端等多个功能模块。 欢迎使用我们的校园快递管理系统&#xff01;我…

前端push.js桌面通知库

push.js 官网&#xff1a;https://pushjs.org/ 安装 1,npm 安装方式 npm install push.js --save 2,script引入方式 <script src"https://cdnjs.cloudflare.com/ajax/libs/push.js/0.0.11/push.min.js"></script> 使用 1&#xff0c;获取用户许可…

2024年 快速搭建自己AI Gemini API 搭建完整

先看下效果 体验效果 Gemini 前言 12月7日消息&#xff0c;谷歌12月6日宣布推出其认为规模最大、功能最强大的人工智能模型Gemini。Gemini将包括三种不同的套件&#xff1a;Gemini Ultra&#xff0c;Gemini Pro和Gemini Nano。 谷歌表示&#xff0c;该公司备受期待的人工智能…

2024年【煤炭生产经营单位(安全生产管理人员)】证考试及煤炭生产经营单位(安全生产管理人员)模拟考试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 煤炭生产经营单位&#xff08;安全生产管理人员&#xff09;证考试是安全生产模拟考试一点通总题库中生成的一套煤炭生产经营单位&#xff08;安全生产管理人员&#xff09;模拟考试题&#xff0c;安全生产模拟考试一…

Spark二、Spark技术栈之Spark Core

Spark Core spark核心&#xff1a;包括RDD、RDD算子、RDD的持久化/缓存、累加器和广播变量 学习链接&#xff1a;https://mp.weixin.qq.com/s/caCk3mM5iXy0FaXCLkDwYQ 一、 RDD 1.1 为什么要有RDD 在许多迭代式算法(比如机器学习、图算法等)和交互式数据挖掘中&#xff0c;…

力扣hot100 翻转二叉树 递归

&#x1f468;‍&#x1f3eb; 题目地址 &#x1f60b; AC code /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNod…

Unity 基于UDP实现本地时间与网络时间校验 防客户端修改日期作弊

新建一个Unity GameObject 挂上NTPComponent脚本 时间校验 源码 using System.Collections; using System.Collections.Generic; using UnityEngine; using System; using UnityEngine.Networking; using System.Text; using System.Net.Sockets; using System.Net; using Sys…

【Nodejs】基于Promise异步处理的博客demo代码实现

目录 package.json www.js db.js app.js routes/blog.js controllers/blog.js mysql.js responseModel.js 无开发&#xff0c;不安全。 这个demo项目实现了用Promise异步处理http的GET和POST请求&#xff0c;通过mysql的api实现了博客增删改查功能&#xff0c;但因没有…

vue3中pdf打印问题处理

1 get请求参数问题 之前的请求是post得不到参数&#xff0c;今天发现的问题很奇怪&#xff0c;从前端进入网关&#xff0c;网关居然得不到参数。 前端代码 const print () > {let linkUrlStr proxy.$tool.getUrlStr(proxy.$api.invOrder.psiInvOrder.printSalOutstock,{a…

Nougat:科学文档的OCR 使用记录

https://github.com/facebookresearch/nougat python环境需要在3.8以上 安装&#xff1a;pip install nougat-ocr 模型默认下载地址&#xff1a;/home/****/.cache/torch/hub/nougat-0.1.0-small 环境安装好之后默认使用cpu UserWarning: CUDA initialization: The NVIDIA dr…

基于决策树、随机森林和层次聚类对帕尔默企鹅数据分析

作者&#xff1a;i阿极 作者简介&#xff1a;数据分析领域优质创作者、多项比赛获奖者&#xff1a;博主个人首页 &#x1f60a;&#x1f60a;&#x1f60a;如果觉得文章不错或能帮助到你学习&#xff0c;可以点赞&#x1f44d;收藏&#x1f4c1;评论&#x1f4d2;关注哦&#x…