首页 > 代码库 > [考研系列之数据结构]线性表之队列

[考研系列之数据结构]线性表之队列

2024-07-06 17:07:51   229人阅读

基本概念


队列的定义队列是一种只能在表的一头插入，另一头删除的线性表，简而言之具有FIFO的特性
组成
队头
队尾
扩展双端队列只能在两端进行删除插入操作的线性表
实现
链队列
顺序队列循环队列

循环队列

循环队列是将顺序队列臆造成一个环，如图



循环队列有以下参数

front指向队头的指针
rear指向队尾的指针
SIZE循环最大队列长度

对于循环队列，初始状态的时候
front=rear=0;
每次insert的时候
Insert((front++)%SIZE);
那么，当循环队列正要插入最后一个元素使得队列满的时候，front=SIZE-1,当执行完Insert后front=rear=0;
我们发现空状态和满状态竟然无法区分，这显然是无法容忍的，针对这个问题，有两种解决方案
[1] 设立一个boolean的标志位表示是空还是满
[2] 少用一个元素空间，rear指向第一个元素的上一个位置
一般情况下我们使用[2]来解决这个问题


联系
我们