队列部分整理
队列
队列特点
- 先进先出
- 一端插入一端删除
顺序存储(对头指针+队尾指针+存放队列元素)
定义
- 设置一个队首指针front,一个对位指针rear,分别指向对首和队尾元素
示意图
操作
- 初始化:front=rear=0
- 判断空:front=rear
- 判断满:rear=MAX_QUEUE_SIZE-1或者front=rear
- 入队:新元素插入到rear所指的位置,然后rear+1
- 出队:删去front所指的元素,然后加1并返回删除元素
假溢出:数组中含有可用的存储空间却无法入队
含义
- 尽管队列中实际元素个数可能远远小于数组大小,但可能由于为指针已超出向量空间的上界而不能做入队操作
原因
- 因为在入队和出队操作中,头尾指针只增加不减小,致使被删除的元素的空间永远无法重新利用
注
- 注:因为入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时都有front=real。所以无法用front=real来判断循环队列队空或队满
解决方法1(了解一下)
- 设置标志位flag,当flag=0且real=front时为空,flag=1且real=front时为满
当入队是令flag=1,出队时flag=0
解决方法2(关注这种)
- 我们吧front=real仅作为队空的判定条件。当队满时,令数组中仍保留一个空单元,real指向这个空单元
循环队列(克服“假溢出“)
定义
将队列分配的向量空间看做一个首尾相接的圆环,并将这种队列称为循环队列
操作
- 初始化:front=rear=0
- 判断空:front=real
链式存储
操作
入队
思想
- 1、分配结点指针S,赋值,新结点后继指针为null
- 2、表尾的后继指针指向新结点Q.rear->next=S
- 3、修改表的后继指针为S,Q.rear=S
出队
思想
- 1、先判断队列是否为空,空返回false
- 2、将头结点的后继结点出队,修改头结点的后继改为它后面的结点
- 3、判断是否原队列只有一个结点,若只有一个,删除变空,
if(Q.rear==p) Q.rear=Q.front - 4、释放p