|
顺序队列 顺序队列 ()顺序队列的定义 队列的顺序存储结构称为顺序队列顺序队列实际上是运算受限的顺序表 () 顺序队列的表示 ①和顺序表一样顺序队列用一个向量空间来存放当前队列中的元素 ②由于队列的队头和队尾的位置是变化的设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置它 们的初值在队列初始化时均应置为 () 顺序队列的基本操作 ①入队时将新元素插入rear所指的位置然后将rear加 ②出队时删去front所指的元素然后将front加并返回被删元素 注意 ①当头尾指针相等时队列为空 ②在非空队列里队头指针始终指向队头元素尾指针始终指向队尾元素的下一位置 顺序队列基本操作【 参见动画演示 】 ()顺序队列中的溢出现象 ① 下溢现象 当队列为空时做出队运算产生的溢出现象下溢是正常现象常用作程序控制转移的条件 ② 真上溢现象 当队列满时做进栈运算产生空间溢出的现象真上溢是一种出错状态应设法避免 ③ 假上溢现象 由于入队和出队操作中头尾指针只增加不减小致使被删元素的空间永远无法重新利用当队列中实际的元素个数远远小于 向量空间的规模时也可能由于尾指针已超越向量空间的上界而不能做入队操作该现象称为假上溢现象 【例】假设下述操作序列作用在初始为空的顺序队列上 EnQueueDeQueueEnQueueDeQueue… 尽管在任何时刻队列元素的个数均不超过但是只要该序列足够长事先定义的向量空间无论多大均会产生指针越界错误 |
