循环队列知识点及习题
目录
一、知识点
二、练习题
一、知识点
1队列是操作受限的线性表。特性是先进先出，后进后出，比如一个队列的入队顺序是1，2，3，4，那么出队的输出顺序就是1，2，3，4。
2循环队列就是一个环状的空间，有队首指针front和队尾指针rear，按照顺时针的顺序出入队。
当有元素入队，rear指针进1，front指针不变；当有元素出队，rear指针不变，front指针进1。当队里没有元素，front==rear。
3区分队空还是队满的方法
牺牲一个单元。约定队首指针在队尾指针的下一位置作为队满标志
那么(Q.rear+1)%Maxsize==Q.front
%Maxsize这里取模的原因是这是一个循环队列，rear+1大于M的话理解为新的循环
二、练习题
1已知循环队列的存储空间为数组A[21]，front指向队首元素的前一个位置，rear指向队尾元素，假设当前front和rear的值分别为8和3，求该队列的长度。
思路：利用公式（rear-front+Maxsize）%Maxsize
（3-8+21）%21=16
2若用数组A[0...5]实现循环队列，且当前rear和front的值分别为1和5，当从队列中删除一个元素再加入两个元素后，求rear和front的值。
思路：删除元素是出队，front指针进1，rear不变；加入元素是入队，rear指针进1，front不变。
根据题干，rear=1，加入2个元素，rear进2，rear=1+2=3
front=5，删除一个元素，front进1，因为这是循环队列，5后面是0，所以front=0
3假设输入序列为1，2，3，4，5，利用两个队列进行出入队操作，不可能输出的序列是
A. 1,2,3,4,5
B. 5,2,3,4,1
C. 1,2,3,4,5
D. 4,1,5,2,3
思路：排除法来做。设两个队列为Q和S，如下图分配
答案选B