将对头指针front指向链队列的头结点,队尾指针rear指向终端结点。
空队列时,头指针front和尾指针rear都指向头结点。
typedef int QElemType; typedef struct QNode { //结点结构 QElemType data; struct QNode *next; }QNode; typedef struct QNode * QueuePtr; typedef struct { //队列的链表结构 QueuePtr rear;//指向队尾节点 QueuePtr front;//指向对头节点 }LinkQueue; //插入元素e为Q的新的队尾结点 Status EnQueue(QueuePtr Q, QElemType e) { QueuePtr q = (QueuePtr)malloc(sizeof(QNode)); if (!q) { //存储分配失败 exit(OVERFLOW); } q->data = e; q->next = NULL; Q->rear->next = q; Q->rear = q;//队尾指针变为p return OK; } //若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR。 //若链表除头结点外只剩一个元素时,则需将rear指针指向头结点。 Status DeQueue(QueuePtr Q, QElemType *e) { QueuePtr q; if (Q->rear == Q->front) { //空队列 return ERROR; } q = Q->front->next; //q指向第一个结点 *e = q->data; Q->front->next = q->next; if (Q->rear == p) { //若队头就是队尾,删除后,需要将rear指针指向头结点 Q->rear = Q->front; } free(q); return OK; }
总的来说,在可以确定链队列最大长度的情况下,建议使用循环队列。如果无法预估队列的长度,则使用链队列。