首页 > 代码库 > [考研系列之数据结构]线性表之队列
[考研系列之数据结构]线性表之队列
基本概念
| 队列的定义 | 队列是一种只能在表的一头插入，另一头删除的线性表，简而言之具有FIFO的特性 | |
| 组成 | 队头 | |
| 队尾 | ||
| 扩展 | 双端队列 | 只能在两端进行删除插入操作的线性表 |
| 实现 | 链队列 | |
| 顺序队列 | 循环队列 | |
循环队列
循环队列是将顺序队列臆造成一个环，如图
循环队列有以下参数
| front | 指向队头的指针 |
| rear | 指向队尾的指针 |
| SIZE | 循环最大队列长度 |
对于循环队列，初始状态的时候
front=rear=0;
每次insert的时候
Insert((front++)%SIZE);
那么，当循环队列正要插入最后一个元素使得队列满的时候，front=SIZE-1,当执行完Insert后front=rear=0;
我们发现空状态和满状态竟然无法区分，这显然是无法容忍的，针对这个问题，有两种解决方案
[1] 设立一个boolean的标志位表示是空还是满
[2] 少用一个元素空间，rear指向第一个元素的上一个位置
[2] 少用一个元素空间，rear指向第一个元素的上一个位置
一般情况下我们使用[2]来解决这个问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。