队列，链队列，链式存储的队列
采用链式存储的队列称为链队列（linked queue）,队列是运算受限的线性表，即队列的插入和删除位置分别位于表的两端。故需要两个指针来指向这2个特殊位置，即对首指针和队尾指针。
本例采用的是带头结点的链队列，因此对首指针指向头结点，而头结点的指针域指向对首结点。
当为空链队列时，对首指针和队尾指针都指向头结点，头结点的指针域指向空。
代码：
/* * main.c * * Created on: 2012-10-21 * Author: china */#include <stdio.h>#include <stdlib.h>#include <assert.h>/*链式队列的定义如下所示*/typedef int datatype;typedef struct SNode {datatype data;struct SNode* next;} QNode,*LinkList;typedef struct {LinkList front; //队首结点(即删除点)LinkList rear; //队尾结点(即插入点)} LinkQueue;int creat_empty_linkqueue(LinkQueue* queue) {LinkList head = (LinkList) malloc(sizeof(QNode));if (NULL == head)return -2;head->next = NULL;queue->front = queue->rear = head;return 1;}int linkqueue_empty(const LinkQueue* queue) {return queue->front == queue->rear;}int linkqueue_length(const LinkQueue* queue) {int len = 0;LinkList p = queue->front;while (p != queue->rear) {p = p->next;len++;}return len;}int linkqueue_get_top_element(const LinkQueue* queue, datatype* e) {if (linkqueue_empty(queue)) {return -1;}*e = queue->front->next->data;return 1;}//入列int linkqueue_enter(LinkQueue* queue, datatype e) {LinkList q = (LinkList) malloc(sizeof(QNode));if (NULL == q)return -2;q->data = e;q->next = NULL;queue->rear->next = q; //修改队尾节点的指针域，使其指向新的队尾结点queue->rear = q; //修改队尾指针使其指向新的队尾结点return 1;}//出列int linkqueue_delete(LinkQueue* queue, datatype* e) {//方法1,(不符合队列的删除特性只在表头进行删除，即只操作对首指针front)if (linkqueue_empty(queue)) {return -1; //空队列}LinkList q = queue->front->next; //q指向将要被删除的对首结点queue->front->next = q->next; //使头结点的指针域指向被删除的下一个结点//如果删除的是最后一个结点，需要让queue->rear指向链表头结点！！！！if (NULL==q->next) {queue->rear=queue->front;}*e = q->data; //返回被删除对首元素的值free(q);q = NULL;return 1;//方法2/* LinkList p = queue->front; queue->front = p->next; free(p); return queue->front->data; */}/*------------------------ 操作目的： 清空队列(使其只留下一个头结点) 初始条件： 队列queue已存在 操作结果： 将队列清空 函数参数： LinkQueue *queue 队列queue 返回值： 无 ------------------------*/void linkqueue_clear(LinkQueue *queue) {//方法1/*assert(queue ->front != NULL);LinkList p = queue->front->next;while (p) {queue->front->next = p->next;free(p);p = queue->front->next;printf("========clear()========\n");}*///方法2datatype e;while(!linkqueue_empty(queue)){linkqueue_delete(queue,&e);}}/*------------------------ 操作目的： 销毁队列(即删除所有的节点包括头结点) 初始条件： 队列queue已存在 操作结果： 销毁队列queue 函数参数： LinkQueue *queue 待销毁的队列 返回值： 无 ------------------------*/void DestroyQueue(LinkQueue* queue) {assert(queue != NULL);while (queue->front) {queue->rear = queue->front->next;free(queue->front);queue->front = queue->rear;printf("================destroy================\n");}}int main(int argc, char **argv) {int i;datatype e, top_e;LinkQueue queue;creat_empty_linkqueue(&queue);if (linkqueue_empty(&queue)) {printf("empty\n");} else {printf("not empty\n");}printf("link queue length is:%d\n", linkqueue_length(&queue));printf("start enter element to link queue\n");for (i = 0; i < 5; i++) {linkqueue_enter(&queue, i + 1);}if (-1 != linkqueue_get_top_element(&queue, &top_e)) {printf("the top of link queue element is:%d\n", top_e);}if (linkqueue_empty(&queue)) {printf("empty\n");} else {printf("not empty\n");}printf("link queue length is:%d\n", linkqueue_length(&queue));printf("start delete element to link queue and the delete element are:\n");for (i = 0; i < 3; i++) {linkqueue_delete(&queue, &e);printf("%d\t", e);}printf("\n");if (linkqueue_empty(&queue)) {printf("empty\n");} else {printf("not empty\n");}printf("link queue length is:%d\n", linkqueue_length(&queue));linkqueue_clear(&queue);DestroyQueue(&queue);return 0;}
运行结果：
emptylink queue length is:0start enter element to link queuethe top of link queue element is:1not emptylink queue length is:5start delete element from link queue and the delete element are:123not emptylink queue length is:2========clear()================clear()========================destroy================