数据结构之队列

3.4 队列

3.4.1 抽象的数据类型队列的定义

和栈相反,队列是一种先进先出(first in first out,缩写为FIFO)的线性表,它只允许在表的一端进行插入,而在表的另一端删除元素。

这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。在队列中,允许插入的一端叫做队尾(rear),允许删除的一端则称为队头。

队列的操作与栈的操作类似,也有8个,不同的是删除是在表的头部(即队列)进行。

双端队列

双端队列是限定插入和删除操作在表的两端进行的线性表。这两个端分别为称作 端点1和端点2

在实际的使用中,还可以有:

输出受限的双端队列(一个端点允许插入和删除,另一个端点只允许插入)

输入受限的双端队列(一个端点允许插入和删除,另一个端点只允许删除)

3.4.2 链队列---队列的链式表示和实现

和线性表类似,队列也可以有两种存储表示。

用链表表示的队列简称链队列。一个链队列显然需要两个分别指示队头和队尾的指针(分别称之为头指针和伪指针)才能唯一确定。

这里和线性表一样,为了操作方便起见,我们给链队列添加一个头结点,并令头指针指向头结点,由此,空的链队列的判决条件为头指针和尾指针均指向头结点。

链队列的操作即为单链表的插入和删除操作的特殊情况,只是尚需修改尾指针或头指针。

程序

(程序框可以左右滑动哦~)

执行结果:

3.4.3 循环队列---队列的顺序表示和实现

循环队列和 一般的队列的区别在于:

如图所示,和顺序栈类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队头和队尾的位置之外,

尚需附设两个指针front 和 rear 分别指示队头元素及队尾元素的位置。为了在C语言中描述方便起见,再次约定:

初始化建空队列时,令front=rear=0,

每当插入新的队列尾元素时,“尾指针之增1”;

每当删除队列头元素时,“头指针增1”

因此,在非空队列中,头指针始终队列头元素,而尾指针始终指向队尾元素的下一个位置。

但是当出现如图d的情况时,队尾已经将已有的空间用尽,同时队头也马上追平队尾

如果继续插入新的元素,程序会因为数组越界而被破坏,然而此时又不宜如顺序栈那样,进行存储再分配扩大数组(因为队列的可用空间并未占满)。

优点:

所以这个时候 循环队列的作用就体现出来了,如图所示:

这时出现一个问题,Q.front == Q.rear 无法判别队列空间是 “空” 还是“满”

处理这种情况的方法一般有两种:

1. 再设一个标志位以区别队列是“空” 还是“满”

2. (强烈推荐)少用一个元素的空间,约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列 “满”状态的标志

缺点:

从上述分析可见,在C语言中不能用动态分配的一维数组来实现。

如果用户的应用程序设有循环队列,则必须为它设定一个最大队列长度;若用户无法预估所用队列的最大长度,则宜采用链队列。

程序

(程序框可以左右滑动哦~)

执行结果:

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

同媒体快讯

扫码关注云+社区

领取腾讯云代金券

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