链队列

1、 链队列的定义
   队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。

2、 链队列的结构类型说明

ld1
注意:
增加指向链表上的最后一个结点的尾指针,便于在表尾做插入操作。
链队列示意图见上图,图中Q为LinkQueue型的指针。

3、 链队列的基本运算
(1) 置空队
void InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=NULL;
}
(2) 判队空
intQueueEmpty(LinkQueue *Q)
{
return Q->front==NULL&&Q->rear==Null;
//实际上只须判断队头指针是否为空即可
}

(3) 入队
       void EnQueue(LinkQueue *Q,DataType 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;           //队尾指针指向新的尾
}
}

(4) 出队
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;  //返回原队头数据
}

(5) 取队头元素
DataType QueueFront(LinkQueue *Q)
{
if(QueueEmpty(Q))
Error(“Queue if empty.”);
return Q->front->data;
}
注意:
①和链栈类似,无须考虑判队满的运算及上溢。
②在出队算法中,一般只需修改队头指针。但当原队中只有一个结点时,该结点既是队头也是队尾,故删去此结点时亦需修改尾指针,且删去此结点后队列变空。
③以上讨论的是无头结点链队列的基本运算。和单链表类似,为了简化边界条件的处理,在队头结点前也可附加一个头结点,增加头结点的链队列的基本运算

Tagged on:

发表评论