|
|
知识路径： > 计算机科学基础 > 常用数据结构 > 队列、栈 > 队列 >
|
|
考试要求：掌握
相关知识点：6个
|
|
|
|
|
顺序存储结构采用一维数组（向量）实现，设队列头指针front和队列尾指针rear，并且假设front指向队头元素的前一位置，rear指向队尾元素。若不考虑队满，则入队操作语句为Q[rear++]=x；若不考虑队空，则出队操作语句为x=Q[++front]。当然，出队时，并不一定需要队头元素（与退栈类似）。
|
|
|
|
按上述的做法，有可能出现假溢出，即队尾已到达一维数组的高端，不能再入队，但因为连续出队，队列中元素个数并未达到最大值。解决这种问题，可用循环队列。在循环队列中，需要区分队空和队满：仍用front=rear表示队列空，在牺牲一个单元的前提下，用front==（rear+1）% MAX表示队列满。在这种约定下，入队操作的语句为：rear=（rear+1）%MAX, MAX, Q[rear]=x；出队操作语句为：front=（front+1）% MAX。
|
|
|
|
|
|
|
|
顺序队列定义为一个结构类型，该类型变量有3个数据域：data、front、rear。其中data为存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量，取值范围是0~QueueSize-1。约定队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示队头元素在一维数组中的当前位置的前一个位置，这种顺序队列说明如下。
|
|
|
|
.初始化时，设置SQ.front=SQ.rear=0。
|
|
|
|
.队头指针的引用为SQ.front，队尾指针的引用为SQ.rear。
|
|
|
|
.队空的条件为SQ.front==SQ.rear；队满的条件为SQ.front=（SQ.rear+1）% QueueSize。
|
|
|
|
.入队操作：在队列未满时，队尾指针先加1（要取模），再送值到队尾指针指向的空闲元素。出队操作：在队列非空时，队头指针先加1（要取模），再从队头指针指向的队头元素处取值。
|
|
|
|
.队列长度为（SQ.rear+QueueSize-SQ.front）% QueueSize。
|
|
|
|
特别应注意的是：在循环队列的操作中队头指针、队尾指针加1时，都要取模，以保持其值不出界。
|
|
|
|
|
|
1）初始化initqueue（SQueue *SQ）
|
|
|
|
|
|
2）判空QueueEmpty（SQueue SQ）
|
|
|
|
|
|
3）入队EQueue（SQueue *SQ, ElemType e）
|
|
|
|
|
|
4）出队OQueue（SQueue *SQ, ElemType *e）
|
|
|
|
|
|
5）取队首元素GetQhead（SQueue *SQ, ElemType *e）
|
|
|
|
|
|
6）清队列ClearQueue（SQueue *SQ）
|
|
|
|
|
