问答题 什么是队列的上溢?怎样解决这个问题?
【正确答案】队列若采用顺序结构,一般易发生上溢。设队首指针为front,队尾指针为rear,队列的容量为MAXSIZE。当一个顺序结构的队列,在经过频繁的入队和出队操作以后,若rear=MAXSIZE,即队尾指针已到达顺序表的顶部,此刻再要入队已不可能,这种情况称为上溢。但上溢并不等于顺序表已无空间,如果队首指针前面有空闲空间,这种情况又称为假溢出。
   解决上溢或假溢出问题的方法有多种:其一,可建立一个足够大的存储空间以避免上溢,但这会造成空间利用效率下降;其二,将队首指针固定在队列低端,入队时队尾指针向高端移动,只要有出队,就将整个队列向低端移动一个元素位置,但这样会造成算法较为复杂;其三,将顺序表首尾相衔接,构成循环结构,称为循环队列。在循环队列中,规定rear=front是循环队列空的标志,(rear+1)/%MAXSIZE=front是循环队列满的标志,入队时rear=(rear+1)/%MAXSIZE,出队时front=(front+1)/%MAXSIZE,这种方法既节省存储空间,算法亦较简单。
【答案解析】