|
链队列 链队列的定义 队列的链式存储结构简称为链队列它是限制仅在表头删除和表尾插入的单链表 链队列的结构类型说明
注意 增加指向链表上的最后一个结点的尾指针便于在表尾做插入操作 链队列示意图见上图图中Q为LinkQueue型的指针 链队列的基本运算（） 置空队 void InitQueue(LinkQueue *Q) { Q>front=Q>rear=NULL; } （） 判队空 intQueueEmpty(LinkQueue *Q) { return Q>front==NULL&&Q>rear==Null; //实际上只须判断队头指针是否为空即可 } （） 入队 void EnQueue(LinkQueue *QDataType x) {//将元素x插入链队列尾部 QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点 p>data=x; p>next=NULL; if(QueueEmpty(Q)) Q>front=Q>rear=p; //将x插入空队列 else { //x插入非空队列的尾 Q>rear>next=p; //*p链到原队尾结点后 Q>rear=p; //队尾指针指向新的尾 } } （） 出队 DataType DeQueue (LinkQueue *Q) { DataType x; QueueNode *p; if(QueueEmpty(Q)) Error(Queue underflow);//下溢 p=Q>front; //指向对头结点 x=p>data; //保存对头结点的数据 Q>front=p>next; //将对头结点从链上摘下 if(Q>rear==p)//原队中只有一个结点删去后队列变空此时队头指针已为空 Q>rear=NULL; free(p); //释放被删队头结点 return x; //返回原队头数据 } （） 取队头元素 DataType QueueFront(LinkQueue *Q) { if(QueueEmpty(Q)) Error(Queue if empty); return Q>front>data; } 注意 ①和链栈类似无须考虑判队满的运算及上溢 ②在出队算法中一般只需修改队头指针但当原队中只有一个结点时该结点既是队头也是队尾故删去此结点时亦需修改尾指针且删去此结点后队列变空 ③以上讨论的是无头结点链队列的基本运算和单链表类似为了简化边界条件的处理在队头结点前也可附加一个头结点增加头结点的链队列的基本运算【参见练习】 |
