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

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

一、队列简介：

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

二、链队：

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

结点定义

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

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

队列头尾指针

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

初始化

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

添加元素示意图

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

添加元素函数

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

删除元素示意图

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

删除读取元素函数

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

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

二、非循环队列：

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

定义队列结构体

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

示意图

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

初始化函数

短短几行代码，简单吧！

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

添加元素函数

我没啥可说的了，太简洁（单）了，下面在看一下删除并读取数据元素的代码：

读取元素函数

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