队列之单向队列

队列之单向队列

本文是看孔浩、张华杰、陈猛编著的《C指针编程之道》所作。

队列,是一种数据结构。顾名思义,就是像排队一样。日常生活中,排队是常见的事情,买票要排队、打饭要排队、坐车要排队……这么细数,貌似任何事都要排队。

队列,是特殊的线性表。因为单链表、双链表,以及顺序线性表,都是没有限制操作位置的,而队列却有这个限制。规定队列只能从一端插入,另一端删除。插入的一端称为队尾,删除的一端称为队头。也就是说,先进队的数据,先出队,后进的数据后出,即所谓的FIFO。这就是它的特殊之处。

队列有多种实现方式,可以用顺序线性表实现,也可以用链表实现。多种队列,各有利弊。

单向队列

有头有尾的队列,又称为单向队列。单向队列,可以通过数组或单向链表来实现。根据队列的定义,队列元素只能在队尾插入,在队头删除。队列用数组来实现时,数组的长度就是队列的最大容量。用单链表来实现时,链表的头节点就是队列的队头,链表的尾节点就是队列的队尾。由于队列必须在队尾、队头两个不同的地方进行插入、删除操作,所以,需要两个不同的指针,分别指向队尾、队头。一般情况,分别用 front、rear指向队头、队尾。

很显然,队列的操作一开始就引入了指针的概念,其重要性可想而知。

对于front，rear的指向,有两种不同的说法,一是font指向队头的前一个位置,rear指向队尾;一是指向队头的位置,rear指向队尾待插入数据的位置。不管使用哪种说法,在编程时要使用同一标准,以免进行判断操作时混乱。本文均以后者为准。

为了有个感性认识,我们先来看看队列的示意图,如图所示。

由图可见, front指向队头位置,rear指向队尾待插入的位置。队头是出队的方向,队尾则是进队的方向。这与日常生活中排队是一个道理,很容易理解。

队列的基本操作有队列初始化、入队、出队、判队空、判队满等。

队列初始化

队列初始化,是建队后的第一步。建队的意思是, 如果采用数组实现,则定义一个数组;如果是静态链表实现,则定义一个数组和节点类型;如果是动态链表实现,则是定义一个链表节点。队列初始化,目的是让font、rear指向队尾的同一个位置,表示队列为空。初始化后,队列为空,如图所示：

入队

如果有数据data5入队,则存放在rear所在的位置,然后rear再加1指向下一个待插入的位置如图所示。

由图可知,data5插入后,rear移动到下一个待插入的的位置,同时刚刚插入的data5成了新的队尾。在整个过程中,指向队头的 front始终不变。

出队

出队操作,与入队操作完全不同,出队操作在队头font端进行。数据出队后, front指向新的队头,即出队数据的下一个数据位置。在这个过程中队尾rear不变。
假设图(b)中,数据data1出队, datal出队后, front指向data2,成为新的队头。 datal出队后,如下图所示：

判队空

单向队列判断队是否为空,比较简单。前面已经介绍, front、rear分别指向队头、队尾。因此很容易得知,当 front、rear指向同一个位置时,即 front==rear时,队列为空。空队列类似于初始化后的队列一样,队头、队尾是同一个位置,也即 front、rear指向同一个位置。

判队满

队列空间有限,不能无限制地插入数据,所以每次插入前要判断队列是否满了。那怎么判断呢?如下图所示,假如队列用数组来实现,数组长度为6。假设要插入数据data7。

data7入队时,判断队列是否已经满了。从图中可知,队尾指针rear指向的位置已经超出了队列的范围,按照只能从队尾入队的原则,这时无法再让data7入队了,貌似队列已经满了。但实际上,队列的[0]、[1]位置为空。这种队头有空位置,队尾没有空位无法再继续入队的现象,称为“假溢出”。

这种情况下,明显队头有空位,队尾却无法再继续插入,让编程人员无法接受。于是,有人建议把所有数据往队头移动。这是一种办法,但往往要花费大量时间。这种“假溢出”的现象,是单向队列的鸡肋,也是众多编程人员不愿使用单向队列的原因。