C语言数据结构中队列的实现与操作

前面介绍过栈,它有着后进先出的特点,今天介绍的队列其特点是先进先出,他们都在实际开发中应用广泛,今天主要先介绍链队跟非循环队列,明天继续介绍循环队列,其实都比较简单,这些在数据结构中很基础,当然还有一种形式的队列,那就是双端队列,但是双端队列并不常用,因此暂时不坐讨论。

一、队列简介:

除去双端队列,一般形式的队列,只能在表的一端(表尾)添加数据元素,而在表的另一端(表头)只能删除数据元素,这些操作也是线性表操作的子集,因此就很简单。当然队列也可以用链表实现,也可以顺序实现,下面就先从链队开始讲起。

二、链队:

既然是链嘛,那么我们肯定需要定义一个结构体来表示每个数据元素的结点,当然我们就简单定义一个,如下:

结点定义

其中ElemT是用#define定义的宏,可以是整型、字符型、同样也可以是结构体类型,这里我们代表整型。第二个next指针想必大家都知道,用于链接两结点。

当然了,既然是队列嘛,由上面队列简介,那么我们还需要两个指针,来分别指向头跟尾,那么我们还用结构体类型来定义,如下:

队列头尾指针

这样基本的定义已经好了,现在主要开始构造链队了,首先我们需要一个结点,来代表初始情况,但是该结点中数据区并不存放元素,只代表初始情况。下面看代码:

初始化

可以看到头尾指向同一结点,并且把该结点中next指针赋值为空。其实很简单,下面看一下如何添加元素,先看一下示意图:

添加元素示意图

图上,我们添加元素时是向下延伸的,下面是队尾,可以看到,要想添加新元素,那么必须先创建一个新结点,然后让上一个next指针指向新创建的结点,而后改变队尾,让队尾指针重新指向新结点。实现函数如下:

添加元素函数

简短的代码,可以看出很简单。下面看一看删除操作示意图:

删除元素示意图

上面示意图说的很清楚我们该函数该怎么写,先看看函数中的内容:

删除读取元素函数

首先创建一个局部指针,然后检查该队列是否为空,然后呢,把第一个存有数据的结点赋给局部指针,然后在把数据元素取出给e,然后把头指针指向下下个结点,然后检查下下个结点是否结束最后一个尾指针,如果是,那么令两指针相等,释放空间,每次读取玩一个结点的数据,应该将该结点所占的内存空间释放。

要是你还不懂,那么说明你知识不牢,思考不够。

二、非循环队列:

该种队列元素占用一组连续的内存单元,所以我们可以定义队列的结构体,下图:

定义队列结构体

我们定义的结构体里面包含一个基址,一个头指针,一个尾指针,当然你完全可以使用数组,而不用指针,这里我们就使用指针吧,至于队列的初始化,我们看下图:

示意图

第一个长条代表内存,我们可以先定一个长度,然后让头尾指针都等于基址,这样就初始化了,下面看一下初始化函数:

初始化函数

短短几行代码,简单吧!

下面就该添加数据元素了,基址不变,每添加一个元素,尾指针增加1,最后还要检查是否到达最大长度,暂且不管头指针,下面我们看看相关函数:

添加元素函数

我没啥可说的了,太简洁(单)了,下面在看一下删除并读取数据元素的代码:

读取元素函数

首先判断是否为空,如为空返回0,然后检测是否到达最大容量,我们这里选择释放这片内存空间,然后检测一般情况下是否读取完毕,最后把数据元素赋给e。上面有一个问题,为啥我们没有向栈那样空间不够再重新申请,当然你可以这样,不过不太好,下面被用完的空间完全可以再用,何必那样呢,下面循环队列就可以解决这种问题。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180311A0JYJ500?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励