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

顺序存储:利用一组连续的存储单元存放从队头至队尾的数据元素。采用顺序存储结构的队列称为“顺序队列(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 (队列容量) 时，将无法入队，但事实上队列中仍有空闲空间，该现象称为“假溢”。

解决方法

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