单队列的链式表示和实现

队列是操作受限的线性表，只允许在队尾插入元素，在队头删除元素，为了便于插入元素，设立队尾指针。这样，插入元素的操作与队列长度无关 队列的链式存储结构

typedef struct QNode{QElemType data;QNode *next;}*QueuePtr;struct LinkQueue{QueuePtr front, rear;//队头，队尾指针};

链队列的9个基本操作

void InitQueue(LinkQueue &Q){Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if (!Q.front) exit(OVERFLOW);Q.front->next = NULL;}void DestroyQueue(LinkQueue &Q){while (Q.front)//Q.front不为空{Q.rear = Q.front->next;//Q.rear指向Q.front的下一个结点free(Q.front);//释放Q.front所指结点Q.front = Q.rear;//Q.front指向Q.front的下一个结点}}void ClearQueue(LinkQueue &Q){DestroyQueue(Q);//销毁队列QInitQueue(Q);//重新构造空队列}Status QueueEmpty(LinkQueue Q){;;}int QueueLength(LinkQueue Q){int i = 0;QueuePtr p = Q.front;//p指向头结点while (Q.rear != p)//p所指不是尾结点{i++;p = p->next;//p指向下一个结点}return i;}Status GetHead(LinkQueue Q, QElemType &e){if (Q.front == Q.rear) return ERROR;//队列空QueuePtr p = Q.front->next;//p指向队头结点e OK;}void EnQueue(LinkQueue &Q, QElemType e){//插入元素e为队列Q的新的队尾元素QueuePtr p;p = (QueuePtr)malloc(sizeof(QNode));//动态生成新结点if (!p) exit(OVERFLOW);pe;p->next = NULL;//新结点的指针域为空Q.rear->next = p;//原队尾结点的指针指向新结点Q.rear = p;//尾指针指向新结点}Status DeQueue(LinkQueue &Q, QElemType &e){//若队列Q不空，，删除Q的队头元素QueuePtr p;if (Q.front == Q.rear) return ERROR;//队列空p = Q.front->next;//p指向队头结点e = p->data;//将队头元素的值赋给eQ.front->next = p->next;//头结点指向下一个结点if (Q.rear == p)//删除的是队尾结点Q.rear = Q.front;//修改队尾指针指向头结点（空队列）free(p);//释放队头结点return OK;}void ListTraverse(LinkQueue Q, void(*visit)(ElemType&)){QueuePtr p = Q.front->next;//p指向队头结点while (p)//p指向结点{visit(p->data);p = p->next;}printf(“\n”);}

有时不但是必要的，而且是很有必要的。