09年自考《数据结构》各章要点一[7]

队列(Queue)是一种运算受限的线性表插入在表的一端进行而删除在表的另一端进行允许删除的一端称为队头(front)允许插入的一端称为队尾(rear) 队列的操作原则是先进先出的又称作FIFO表(First In First Out) 队列也有顺序存储和链式存储两种存储结构

队列的基本运算有六种

·置空队InitQueue(Q)

·判队空QueueEmpty(Q)

·判队满QueueFull(Q)

·入队EnQueue(Qx)

·出队DeQueue(Q)

·取队头元素QueueFront(Q)

顺序队列的假上溢现象由于头尾指针不断前移超出向量空间这时整个向量空间及队列是空的却产生了上溢现象

为了克服假上溢现象引入循环向量的概念是把向量空间形成一个头尾相接的环形这时队列称循环队列

判定循环队列是空还是满方法有三种

·一种是另设一个布尔变量来判断

·第二种是少用一个元素空间入队时先测试((rear+)%m = front)? 满空

·第三种就是用一个计数器记录队列中的元素的总数

队列的链式存储结构称为链队列一个链队列就是一个操作受限的单链表为了便于在表尾进行插入(入队)的操作在表尾增加一个尾指针一个链队列就由一个头指针和一个尾指针唯一地确定链队列不存在队满和上溢的问题在链队列的出队算法中要注意当原队中只有一个结点时出队后要同进修改头尾指针并使队列变空

[] [] [] [] [] [] [] [] [] [] []