搜索
写经验 领红包
 > 动物

队列的顺序存储结构及实现实验报告(队列的顺序存储结构及实现实验)

导语:队列的顺序存储结构及实现

顺序存储:利用一组连续的存储单元存放从队头至队尾的数据元素。采用顺序存储结构的队列称为“顺序队列(sequential queue)”。

实现:事先分配一个可以容纳最多元素的存储空间,并且为方便操作,需设置队头(front)、队尾(rear)指针分别指示队头、队尾位置。

如果用两个整型变量front、rear分别表示队头、队尾,且队头指向队首元素位置,队尾指向队尾元素之后,则:

(1) 初始化队列时,rear = front = 0

(2) 入队时,两个基本操作为:

Step 1:若队不满,把入队元素送入rear所指单元

Step 2:移动队尾,即rear = rear+1

(3) 出队时,两个基本操作为:

Step 1:若队不空,从front所指单元取队头元素

Step 2:移动队头,即front = front+1

1.a1 a2 a3 a4依次入队

2.a1 a2依次出队

时间性能改进思路3.a1 a2 a3 a4依次入队

4.a1 a2依次出队

整个队列向数组下标较大方向移动=>单向移动性顺序队列结构及操作示意

假溢

由前图可知,当rear> = queuesize (队列容量) 时,将无法入队,但事实上队列中仍有空闲空间,该现象称为“假溢”。

解决方法

假设存储队列的连续存储空间是头尾相接的环状结构 ,当指针移到最大值后又从最小值开始。

本文内容由快快网络小鸣整理编辑!