队列的链式实现

1 队列的链式存储表示
队列的链式存储结构简称为链队列，它是限制在表头进行删除操作和表尾进行插入操作的单链表。
需要两类不同的结点：数据元素结点，队列的队首指针和队尾指针的结点
指针结点类型定义：

typedef struct link_queue
{   QNode  *front ,  *rear ;
}LinkQueue ;

2 链队运算及指针变化
链队的操作实际上是单链表的操作，只不过是删除在表头进行，插入在表尾进行。插入、删除时分别修改不同的指针

3 链队列的基本操作 ⑴ 链队列的初始化 Status Init_LinkQueue(LinkQueue *Q ) { /*成功返回OK，否则返回ERROR*/ QNode *p ; p=(QNode *)malloc(sizeof(QNode)) ; /* 开辟头结点 */ if(p==NULL) return ERROR; p->next=NULL ; Q->front=Q->rear=p ; return OK; } 

⑵ 链队列的入队操作 在已知队列的队尾插入一个元素e ，即修改队尾指针(Q.rear)。 Status Insert_LinkQueue(LinkQueue *Q , ElemType e) /* 将数据元素e插入到链队列Q的队尾 */ { QNode *p ; p=(QNode *)malloc(sizeof(QNode)) ; if (!p) return ERROR; /* 申请新结点失败，返回错误标志 */ p->data=e ; p->next=NULL ; /* 形成新结点 */ Q->rear->next=p ; Q->rear=p ; /* 新结点插入到队尾 */ return OK; } 

链队列的出队操作 Status Delete_LinkQueue(LinkQueue *Q, ElemType *x) { QNode *p ; if (Q->front==Q->rear) return ERROR ; /* 队空 */ p=Q->front->next ; /* 取队首结点 */ *x=p->data ; Q->front->next=p->next ; /* 修改队首指针 */ if (p==Q->rear) Q->rear=Q->front ; /* 当队列只有一个结点时应防止丢失队尾指针 */ free(p) ; return OK ; } 

⑷ 链队列的撤消 void Destroy_LinkQueue(LinkQueue *Q ) /* 将链队列Q的队首元素出队 */ { while (Q->front!=NULL) {Q-> rear= Q-> front->next; /* 令尾指针指向队列的第一个结点 */ free(Q-> front); /* 每次释放一个结点 */ /* 第一次是头结点，以后是元素结点 */ Q-> front= Q-> rear; } }