队列的链式存储结构
所谓队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已。
为了操作方便，我们将队头指针指向链队列的头结点，而队尾指针指向终点元素，注意这个时候不是尾部元素的下一个了
。如图：
空队列时，头指针front和尾指针rear都指向头结点。
链队列的结构为
1 typedef struct QNode //节点结构
2 {
3 int data;
4 QNode* next;
5 }QNode;
6 typedef struct QNode* QueuePtr;
7 typedef struct{ //队列的链表结构
8 QueuePtr front,rear;
9 }LinkQueue;
队列初始化操作
1 /*链队列初始化操作,初始化头结点*/
2 int InitLinkQueue(LinkQueue* Q){
3 if(!Q)
4 return 0;
5 QueuePtr s =(QueuePtr)malloc(sizeof(QNode));
6 s->next=NULL;
7 Q->front=Q->rear=s; //置空
8 return 0;
9
10 }
队列使用前必须初始化，申请头结点内存空间。
入队操作
1 /*入队操作*/
2 int EnQueue(LinkQueue* Q,int e){
3 QueuePtr s =(QueuePtr)malloc(sizeof(QNode)); //申请新节点空间
4 if(!s)
5 return 0;
6 s->data=e; //赋值
7 //s->next=Q->rear->next; //并初始化,与s->next=NULL相同
8 s->next=NULL;
9 Q->rear->next=s;
10
11 Q->rear=s;
12 return e;
13 }
入队的操作是将新节点指向rear 的next ,然后再将rear 的next指向新节点(类似单链表的插入)，最后确记要把rear移动到新节点
出队操作
1 /*出队操作*/
2 int DeQueue(LinkQueue* Q){
3
4 int e;
5 QueuePtr p;
6 p=Q->front->next; //指向第一个节点
7 if(p){
8 Q->front->next=p->next; //头结点下移
9 free(p); //释放内存
10 p=Q->front->next; //p再移到头结点下
11 }
12 else if(p = Q->rear) //空队列时
13 Q->front = Q->rear;
14
15 return e;
16 }
使用一个指针p指向头结点的下一位，然后移动头结点到p的next，再然后释放p的内存，这就释放的一个节点的空间，此时p再次移动到头结点的下一位，依次进行...
遍历队元素
1 /*遍历队列*/
2 void TraverseQueue(LinkQueue* Q){
3 QueuePtr p;
4 p = Q->front->next;
5 while(p){
6 printf("%d ",p->data);
7 p=p->next;
8 }
9 }
遍历队元素的确记不要去移动front和rear指针的而位置，所以要再新建一个指针来遍历。
清空队
1 /*清空链队列*/
2 int ClearLinkQueue(LinkQueue* Q){
3
4 QueuePtr p;
5
6 p = Q->front->next; //p指向头结点下一个
7 while(p){
8 Q->front->next=p->next; //队头移动
9 if(Q->rear==p) //删到队尾了
10 Q->front = Q->rear; //队列置空
11 else if(Q->front=Q->rear) //循环退出
12 return 0;
13 free(p); //释放内存
14 p=Q->front->next; //继续移动
15 }
16 return 1;
17 }
再清空队列的循环中确记要加上循环结束的出口，否则将陷入死循环，即当Q->real==Q->front时，队列为空 。其中指针的移动类似于出队的操作相同。
主要代码
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 typedef struct QNode //节点结构
5 {
6 int data;
7 QNode* next;
8 }QNode;
9 typedef struct QNode* QueuePtr;
10
11 typedef struct{ //队列的链表结构
12 QueuePtr front,rear;
13 }LinkQueue;
14
15 /*链队列初始化操作,初始化头结点*/
16 int InitLinkQueue(LinkQueue* Q){
17 if(!Q)
18 return 0;
19 QueuePtr s =(QueuePtr)malloc(sizeof(QNode));
20 s->next=NULL;
21 Q->front=Q->rear=s; //置空
22 return 0;
23 }
24
25 /*入队操作*/
26 int EnQueue(LinkQueue* Q,int e){
27 QueuePtr s =(QueuePtr)malloc(sizeof(QNode));
28 if(!s)
29 return 0;
30 s->data=e; //赋值
31 //s->next=Q->rear->next; //并初始化,与s->next=NULL相同
32 s->next=NULL;
33 Q->rear->next=s;
34
35 Q->rear=s;
36 return e;
37 }
38
39 /*清空链队列*/
40 int ClearLinkQueue(LinkQueue* Q){
41
42 QueuePtr p;
43
44 p = Q->front->next; //p指向头结点下一个
45 while(p){
46 Q->front->next=p->next; //队头移动
47 if(Q->rear==p) //删到队尾了
48 Q->front = Q->rear; //队列置空
49 else if(Q->front=Q->rear) //循环退出
50 return 0;
51 free(p); //释放内存
52 p=Q->front->next; //继续移动
53 }
54 return 1;
55 }
56
57
58 /*队列是否为空*/
59 int ElmptyQueue(LinkQueue* Q){
60 QueuePtr p;
61 p=Q->front->next;
62 if(p)
63 return 0;
64 else
65 return 1;
66 }
67
68 /*获取队列长度*/
69 int QueueLength(LinkQueue* Q){
70 int count=0;
71 QueuePtr p;
72 p=Q->front->next;
73 while(p){
74 count++;
75 p=p->next;
76 }
77 return count;
78 }
79
80 /*出队操作*/
81 int DeQueue(LinkQueue* Q){
82
83 int e;
84 QueuePtr p;
85 p=Q->front->next; //指向第一个节点
86 if(p){
87 Q->front->next=p->next; //头结点后移
88 free(p); //释放内存
89 p=Q->front->next; //p再移到头结点下
90 }
91 else if(p = Q->rear) //空队列时
92 Q->front = Q->rear;
93
94 return e;
95 }
96
97 /*遍历队列*/
98 void TraverseQueue(LinkQueue* Q){
99 QueuePtr p;
100 p = Q->front->next;
101 while(p){
102 printf("%d ",p->data);
103 p=p->next;
104 }
105 }
106
107 int main(){
108
109 LinkQueue s;
110 InitLinkQueue(&s);
111 printf("入队10个元素 ：
");
112 for(int i=0;i<10;i++)
113 printf("%d ",EnQueue(&s,i));
114 printf("
");
115
116 printf("遍历队列
");
117 TraverseQueue(&s);
118 printf("
");
119
120 printf("队元素个数");
121 printf("个数：%d
",QueueLength(&s));
122 printf("出队一个元素
");
123 DeQueue(&s);
124 printf("队元素个数");
125 printf("个数：%d
",QueueLength(&s));
126
127 printf("是否队列为空(1:0):%d
",ElmptyQueue(&s));
128
129 printf("清空队列...");
130 ClearLinkQueue(&s);
131 printf("个数：%d
",QueueLength(&s));
132 return 0;
133 }
链式存储结构比顺序结构难操作，特别要注意指针的指向和指向内存的有效性。
比较循环队列和链队列的差异性：
从时间上：两者操作都是O(1)，即常数时间，不过循环队列是事先申请好空间，使用期间不能释放，而对于链队列，每次申请和释放节点也会产生一些时间上的开销
如果入队和出队频繁的话，还是存在细微差异性的，
从空间：循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题了，而链队列不存在此问题，所以在空间上，链队列更加灵活。
附上Java代码
1 package linkqueue; 2 3 public class LinkQueue { 4 5 QNode front, rear; 6 7 /** 8 * 初始化队列 9 */ 10 public void initLinkQueue(LinkQueue Q) { 11 QNode node = new QNode(); 12 node.next = null; 13 Q.front = Q.rear = node; 14 } 15 16 /** 17 * 入队 18 */ 19 public void enLinkQueue(LinkQueue Q, int e) { 20 QNode node = new QNode(); 21 node.data = e; 22 node.next = Q.rear.next; 23 Q.rear.next = node; 24 Q.rear = node; 25 } 26 27 /** 28 * 出队 29 */ 30 public int deLinkQueue(LinkQueue Q) { 31 int e; 32 QNode node; 33 node = Q.front.next; 34 35 if (node != null) { 36 e = node.data; 37 Q.front.next = node.next; 38 node = Q.front.next; 39 return e; 40 } else if (node == Q.rear) { 41 Q.rear = Q.front; 42 } 43 return 0; 44 } 45 46 /** 47 * 清空队 48 */ 49 public void clearLinkQueue(LinkQueue Q) { 50 QNode node; 51 node = Q.front.next; 52 if (node == Q.rear) 53 Q.rear = Q.front = null; 54 while (node != null) { 55 Q.front.next = node.next; 56 node = Q.front.next; 57 } 58 59 } 60 61 /** 62 * 返回队列长度 63 */ 64 public int gtLinkQueue(LinkQueue Q) { 65 int count = 0; 66 QNode node; 67 node = Q.front.next; 68 while (node != null) { 69 count++; 70 node = node.next; 71 } 72 return count; 73 } 74 75 /** 76 * 遍历队元素 77 */ 78 public void traverseList(LinkQueue Q) { 79 QNode node; 80 node = Q.front.next; 81 while (node != null) { 82 System.out.print(node.data + " "); 83 node = node.next; 84 } 85 } 86 87 }
1 package linkqueue; 2 3 public class QNode { 4 int data; 5 QNode next; 6 }
1 package linkqueue; 2 3 public class Test { 4 5 public static void main(String[] args) { 6 LinkQueue queue = new LinkQueue(); 7 System.out.println("初始化队列..."); 8 queue.initLinkQueue(queue); 9 System.out.println("入队10个元素..."); 10 for (int i = 0; i < 10; i++) 11 queue.enLinkQueue(queue, i); 12 System.out.println("遍历队列元素..."); 13 queue.traverseList(queue); 14 System.out.println(""); 15 16 System.out.println("出队一个元素..." + queue.deLinkQueue(queue)); 17 System.out.println("再出队一个元素..." + queue.deLinkQueue(queue)); 18 19 System.out.println("元素个数..." + queue.gtLinkQueue(queue)); 20 21 System.out.println("清空队列"); 22 queue.clearLinkQueue(queue); 23 System.out.println("元素个数..." + queue.gtLinkQueue(queue)); 24 25 } 26 27 }
完毕 - 。-