一 链式队列
数据结构：两个指向节点的指针front, rear;
当链队为空时，front和rear都指向头节点,因此出队时，删除队尾节点时要注意！
link_queue.h
1 typedef int type_t;
2 typedef enum {false, true} bool;
3
4 struct queue_node {
5 type_t data;
6 struct queue_node *next;
7 };
8
9 struct link_queue {
10 struct queue_node *front;
11 struct queue_node *rear;
12 };
13
14 struct link_queue *queue_create();
15 bool enqueue(struct link_queue *q, type_t data);
16 type_t dequeue(struct link_queue *q);
17 bool queue_is_empty(struct link_queue *q);
18 void queue_destroy(struct link_queue *q);
link_queue.c
#include <stdio.h>
2 #include <stdlib.h>
3 #include "link_queue.h"
4
5 struct link_queue *queue_create()
6 {
7 struct link_queue *tmp;
8 struct queue_node *head;
9
10 tmp = malloc(sizeof(*tmp));
11
12 head = malloc(sizeof(*head));
13
14 head->next = NULL;
15
16 tmp->front = head;
17 tmp->rear = head;
18
19 return tmp;
20 }
21
22 bool queue_is_empty(struct link_queue *q)
23 {
24 return q->front == q->rear;
25 }
26
27 bool enqueue(struct link_queue *q, type_t data)
28 {
29 struct queue_node *tmp;
30
31 tmp = malloc(sizeof(*tmp));
32
33 tmp->data = data;
34 tmp->next = NULL;
35 q->rear->next = tmp;
36 q->rear = tmp;
37 }
38
39 type_t dequeue(struct link_queue *q)
40 {
41 type_t tmp;
42 struct queue_node *node;
43
44 if (queue_is_empty(q))
45 return 0;
46 tmp = q->front->next->data;
47 node = q->front->next;
48
49 if (q->front->next == q->rear) //防止把尾指针删掉,链式队列尾指针是指向最后一个节点，而不是最后一个节点的下一个,假设删掉最后一个节点，则q ->rear = NULL；而此时队列为空，front和rear都应指向head!
50 q->rear = q->front;
51
52 q->front->next = node->next;
53
54 free(node);
55
56 return tmp;
57 }
58
59 void queue_destroy(struct link_queue *q)
60 {
61 struct queue_node *tmp = q->front->next;
62
63 while (tmp) {
64 struct queue_node *node = tmp;
65 tmp = tmp->next;
66 free(node);
67 }
68 free(q);
69 }
70
71 int main()
72 {
73 struct link_queue *tmp;
74 int i;
75
76 tmp = queue_create();
77
78 for (i = 1; i <= 10; i++)
79 enqueue(tmp, i);
80
81 while (!queue_is_empty(tmp))
82 printf("%d", dequeue(tmp));
83
84 printf("\n");
85
86 return 0;
87 }
注：链表与链队列的区别是什么？
从代码上看：写链表时仅定义节点就可，然后把节点串联起来！
而写链队时，先定义节点（这样能串成链表），再定义front,rear（这才是队列，这种数据结构）
如果是链栈,先定义节点（这样能串成链表），再定义stack栈顶指针（这才是栈，这种数据结构）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
