前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【数据结构(C语言版)系列三】 队列

【数据结构(C语言版)系列三】 队列

作者头像
闪电gogogo
发布2018-10-10 09:48:53
1.1K0
发布2018-10-10 09:48:53
举报
文章被收录于专栏:闪电gogogo的专栏

队列的定义

队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素。这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。在队列中,允许插入的一端叫做队尾rear),允许删除的一段则称为队头front)。假设队列为q = (a1,a2,...an)则a1就是队头元素,an是队尾元素。

双端队列

除了栈和队列之外,还有一种限定性数据结构是双端队列:限定插入和删除操作在表的两端进行的线性表。两端分别称为端点1和端点2,也可像栈一样,可用一个铁道转轨网络来比喻双端队列。在实际使用中,还可以有输出首先的双端队列(即一个端点允许插入和删除,另一个端点只允许插入的双端队列)和输入首先的双端队列(即一个端点允许插入和删除,另一个端点只允许删除的双端队列)。而如果限定双端队列从某个端点插入的元素只能从该端点删除,则该双端队列就蜕变为两个栈底相邻接的栈了。

尽管双端队列看起来似乎比栈和队列更灵活,但实际上在应用程序中远不及栈和队列有用。

链队列——队列的链式表示和实现

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

用链表表示的队列简称链队列。一个链队列需要两个分别指示队头和队尾的指针,分别称为头指针和尾指针才能唯一确定。为方便起见也给链队列添加一个头结点,并令头指针指向头结点。由此,空的链队列的判决条件为头指针和尾指针均指向头结点。如图所示

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

在初始化建空队列时,约定front = rear = 0,每当插入新的队列尾元素时,尾指针增1,每当删除队列头元素时,头指针增1。因此,在非空队列中,头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一个位置,如图所示:

假设当前为队列分配的最大空间为6,则当队列处于d状态时,不可在继续插入新的队尾元素,否则将导致数组越界。然而此时又不宜如顺序栈那样,进行存储再分配扩大数组空间,因为队列的实际可用空间并为占满。因此提出了循环队列的概念。

如下图所示,队列头元素是J3,队列尾元素是J5,之后6、7、8插入,队列空间占满,有Q.front  = Q.rear,若3、4、5删除,队列空,同样有Q.front  = Q.rear。因此,只凭头指针=尾指针无法判断队列是空还是满,可有两种处理方法:其一是另设一个标志位以区别队列是空还是满;其二是少用一个元素空间,约定以队列头指针在队列尾指针的下一位置(即环状的下一位置)上作为队列满的标志。在C语言中,不能用动态分配的一维数组来实现循环队列,如果用户的应用程序中设有循环队列,则必须为它设定一个最大队列长度,若用户无法预估长度,则宜采用链队列。

附:3-9-模拟银行排队过程-栈和队列-第3章-《数据结构》课本源码-严蔚敏吴伟民版

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-09-12 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 队列的定义
  • 双端队列
  • 链队列——队列的链式表示和实现
  • 循环队列——队列的顺序表示和实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档