顺序队列/链式队列_顺序队列和链式队列的区别-程序员宅基地

技术标签：顺序队列/链式队列 C 出入队列取队首元素销毁队列数据结构

队列是另一种限定性的线性表，他只允许在表的一端插入元素，而在表的另一端删除元素，具有“先进先出”的特点。在队列中，允许插入的一端称为队尾，允许删除的一端称为队首。

与线性表相似，队列也有两种存储结构：顺序队列和链式队列。

一，顺序队列

顺序队列使用顺序表来实现的，即队列中的元素均存放在一片连续的内存空间中。通过该片内存的地址对队列中元素进行访问。之前是用数组来实现顺序表的。通过数组名访问数组元素。数组的长度必须提前设定，一旦超过设定的大小，则无法再向其中添加元素。

这里采用与顺序栈类似的方法，通过设定初始值来动态申请内存，当内存不够用时，修改初始值来再次申请更大的内存达到扩容的目的。所以可以通过动态申请的内存地址来访问队列中的元素。

因此，以下实现的是可以扩容的顺序队列。

1. 顺序队列的结构

要实现扩容的顺序队列，

（1）首先要动态申请一片连续的内存。该内存需要一个指针data指向，通过该指针来访问该内存。

（2）而该内存的大小需提前设定，用capacity进行表示

（3）另外，还需要知道队列中实际元素的个数size

因为队列具有“先进先出”的特点，只能在一端（队尾）进，另一端（队头）出。所以可能造成下面的情况：

此时，需要时刻知道队列两端所在的位置，但又不能像顺序栈一样用size来表示队尾结点所在位置。所以还需要两个变量：（4）head表示队首结点所在的下标

（5）tail表示队尾结点的下个位置所在的下标（这样入队时直接在tail处设置元素即可）。

所以，队列中所有元素的下标所在范围为：[head,tail)，如下图：

代码如下：

typedef char SeqQueueType;
                                                                                                                                                      
//顺序队列的结构
typedef struct SeqQueue
{
    SeqQueueType* data;//指向顺序队列的指针
    int size;//顺序队列的实际长度
    int capacity;//顺序队列的有效长度
    int head;//顺序队列的头节点所在的下标
    int tail;//顺序队列尾节点下个元素所在的下标,即[head,tail)
}SeqQueue;

2. 顺序队列的初始化

在对队列初始化时，首先要设定队列有效长度的初始值，再根据该初始值来动态申请内存，并由data指向。因为此时队列中并没有元素，所以，实际长度size，head和tail均置为0即可。

代码如下：

//初始化顺序队列
void SeqQueueInit(SeqQueue* queue)
{
    if(queue == NULL)
    {
        //非法输入
        return;
    }

    queue->size = 0;//初始时队列为空
    queue->capacity =1000;//设置有效长度为1000
    queue->data = (SeqQueueType*)malloc(queue->capacity*sizeof(SeqQueueType));//动态申请内存,由data指向
    queue->head = 0;//初始时，队列为空

本文链接：https://blog.csdn.net/sandmm112/article/details/79860257

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

PTA 5-10 多项式A除以B (2017cccc初赛L2-2)_pta你需要计算两个多项式相除的商q和余r,其中r的阶数必须小于b的阶数-程序员宅基地

文章浏览阅读2.7k次，点赞4次，收藏3次。5-10多项式A除以B(25分)这仍然是一道关于A/B的题，只不过A和B都换成了多项式。你需要计算两个多项式相除的商Q和余R，其中R的阶数必须小于B的阶数。输入格式：输入分两行，每行给出一个非零多项式，先给出A，再给出B。每行的格式如下：N e[1] c[1] ... e[N] c[N]其中N是该多项式非零项的个数，e[i]是第i个非零项的指数，c_pta你需要计算两个多项式相除的商q和余r,其中r的阶数必须小于b的阶数

【Focal Loss】简单理解及 Pytorch 代码 Focal Loss for Dense Object Detection_focal loss for dense object detection pytorch-程序员宅基地

文章浏览阅读6.9k次，点赞2次，收藏9次。一、首先回顾下“交叉熵loss Cross Entropy Loss” CE(Pi)=-log(Pi)二、一般地说，我们数据集会存在类别不平衡问题，很多人会在loss上对应不同类别设置不同系数 loss就变成了上面的样子三、Focal loss其实就是通过数学公式上的改变，扩大了不平衡因素在loss上的影响..._focal loss for dense object detection pytorch

50个综合资源类导航网站分享_综合导航-程序员宅基地

文章浏览阅读1.1k次。50个综合资源类导航网站分享，你想有的全都有。_综合导航

QDockWidget的关闭事件_qdockwidget关闭触发什么信号-程序员宅基地

文章浏览阅读1.8k次。qt QDockWidget 关闭事件_qdockwidget关闭触发什么信号

04-树5 Root of AVL Tree (25分)_an avl tree is a self-balancing binary search tree-程序员宅基地

文章浏览阅读2k次。An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is_an avl tree is a self-balancing binary search tree…

el+vue 实战 ⑧ el-calendar日历组件设置点击事件、el-calendar日历组件设置高度、el-calendar日历组件自定义日历内部内容_el-calendar点击事件-程序员宅基地

文章浏览阅读1.1w次，点赞8次，收藏41次。日历显示内容变为01，02的形式，点击相应的日期后，有一个弹出框显示当天完成的一些内容。① 其中value在script中定义如下：② 日历组件的data的结构如下：弹出框代码如下，ref绑定的名称同上面命名一样即可。⑤ 调整日历组件的宽高，样式设置三、组件整体代码：四、总结后面这个再慢慢优化吧，前端属实写着比后端有趣，但是后端提升空间大，钱更多........._el-calendar点击事件

随便推点

全球公链进展| Shibarium已上线；opBNB测试网PreContract硬分叉；Sui 主网 V1.7.1 版本_shibarium上线-程序员宅基地

文章浏览阅读1.6k次。Sui 主网现已升级至 V1.7.1 版本，此升级包含了多项修复和优化，包括：协议版本提升至 20 版本，在 Sui 框架中新增 Kiosk Extensions API 和一个新的 sui::kiosk_extension 模块，开发者可使用该 API 构建自定义的 Kiosk 应用程序，以扩展 Kiosk 基本功能；以太坊基金会工程师 Parithosh Jayathi 发推称，Dencun-devnet-8 已上线，这是开发者网络的最新迭代版本，旨在允许客户端与最新规范进行互操作性测试。_shibarium上线

idea显示properties文件中文乱码_idea properties 乱码-程序员宅基地

文章浏览阅读1k次。解决idea显示文件中文乱码在项目中通常会遇到如下问题，突然properties文件中文就显示为\u5730等等这样类似的字符。_idea properties 乱码

【嵌入式实验】南航嵌入式实验报告——GPIO实验_南航nuaa嵌入式系统实验报告-程序员宅基地

文章浏览阅读9.2k次，点赞12次，收藏146次。嵌入式系统原理与应用实验报告-GPIO实验文章目录嵌入式系统原理与应用实验报告-GPIO实验一、实验目的1.1 基于GPIO的LED跑马灯实验1.2 基于GPIO的简单人机交互接口实验1.3 基于GPIO的直流电机控制实验二、实验原理（硬件连接及软件流程、简单原理说明）2.1 实验设备2.2 实验硬件连接图2.3 实验简单原理三、实验内容与实验步骤3.1 基于GPIO的LED跑马灯实验3.1.1 实验内容3.1.2 实验步骤3.1.3 完整实验代码3.2 基于GPIO的简单人机交互接口实验3.2.1 实验_南航nuaa嵌入式系统实验报告

vue3中借助 pdfjs-dist 实现pdf文件展示、文本选中功能及使用过程中部分问题处理_vue3对pdf文件操作文件选取-程序员宅基地

文章浏览阅读2.6k次，点赞30次，收藏30次。一、文件预览1、安装 `pdfjs-dist` ，此处指定版本为 `2.16.105`2、`html` 结构内容3、`js` 功能实现：4、可能出现的问题(1) 部分字体出现乱码或浏览器控制台出现警告二、文本选中1、功能实现2、可能出现的问题：(1) 页面文字可选中，但文本不可见(2) 浏览器控制台报错 `Uncaught (in promise) TypeError: Cannot read properties of undefined (reading 'dispatch_vue3对pdf文件操作文件选取

二叉树的先序+中序+后序的遍历非递归版本_后序遍历,第一个访问的节点-程序员宅基地

文章浏览阅读139次。先序遍历递归版本很简单，学习一下非递归的写法。先遍历根节点，再遍历左儿子，最后遍历右儿子def preOrder(root): # 返回先序遍历序列 if not root: return [] p = root res = [] stack = [] while stack or p: ..._后序遍历,第一个访问的节点

springboot+mybatis+dubbo+redis简单整合_springboot、dubbo和mybatisplus和redis搭建工程如何自动生成pom依赖-程序员宅基地

文章浏览阅读3.7k次，点赞2次，收藏11次。一、创建一个接口maven项目里面存放服务的接口与实体类，在本地仓库安装（install）一下接口服务，目录结构User就是简单的pojo实体类，在UserService中提供了两个接口方法package com.fhh.springboot.service;import com.fhh.springboot.Entity.User1;/** * 功能描述：（..._springboot、dubbo和mybatisplus和redis搭建工程如何自动生成pom依赖