Queue队列

队列，和栈相反 FIFO&LILO。有两个端点，rear 和 front，插入在rear之后插入，删除在front。

可以用 array 和 linked list 实现，至于各自的优缺点，之前写的有。这里就不再赘述了

array

静态的

linked list

动态的

array 实现

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 struct queue
 5 {
 6     int front, rear, size;
 7     unsigned capacity;
 8     int * array;
 9 };
10 struct queue * creatQueue(int capacity)
11 {
12     struct queue * q = (struct queue *)malloc(sizeof(struct queue));
13     q->capacity = capacity;
14     q->front = 0;
15     q->rear = capacity - 1;
16     //这样也可以
17     //q->rear = 0;
18     q->size = 0;
19     q->array = (int *)malloc(capacity * sizeof(int));
20 
21     return q;
22 }
23 int isEmpty(struct queue * q)
24 {
25     return 0 == q->size ? 1 : 0;
26 }
27 int isFull(struct queue * q)
28 {
29     return q->capacity == q->size ? 1 : 0;
30 }
31 void enQueue(struct queue * q, int data)
32 {
33     if(isFull(q))
34     {
35         printf("
The Queue is Full");
36         return ;
37     }
38     else
39     {
40         //这里刚开始不懂，数组的下标是从0开始的，写成下面那种方式也可以，不知道为什么要写成这样
41         q->rear = (q->rear + 1) % (q->capacity);
42         //q->array[q->rear++] = data;
43         q->array[q->rear] = data;
44         q->size += 1;
45         printf("
%d enqueued to Q and rear = %d", data, q->rear);
46     }
47 }
48 int deQueue(struct queue * q)
49 {
50     int num;
51 
52     if(isEmpty(q))
53     {
54         printf("
The Q is empty");
55         return 0;
56     }
57     else
58     {
59         num = q->array[q->front];
60         q->front = (q->front +1 ) % (q->capacity);
61         q->size -= 1;
62         printf("
 front = %d", q->front);
63         return num;
64     }
65 }
66 int getFront(struct queue * q)
67 {
68     return q->array[q->front];
69 }
70 int getRear(struct queue * q)
71 {
72     return q->array[q->rear];
73 }
74 int main(void)
75 {
76     struct queue * q = creatQueue(5);
77 
78     enQueue(q, 1);
79     enQueue(q, 2);
80     enQueue(q, 2);
81     enQueue(q, 3);
82     enQueue(q, 4);
83     enQueue(q, 5);
84 
85     printf("
%d dequeue off Q", deQueue(q));
86     printf("
%d dequeue off Q", deQueue(q));
87     printf("
%d dequeue off Q", deQueue(q));
88     printf("
%d dequeue off Q", deQueue(q));
89     printf("
%d dequeue off Q", deQueue(q));
90     printf("
%d dequeue off Q", deQueue(q));
91     return 0;
92 }

linked list实现

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 struct node
 5 {
 6     int data;
 7     struct node * next;
 8 };
 9 struct queue
10 {
11     struct node * rear, * front;
12 };
13 struct node * creatNode(int data)
14 {
15     struct node * new_node = (struct node *)malloc(sizeof(struct node));
16     new_node->data = data;
17     new_node->next = NULL;
18 
19     return new_node;
20 }
21 struct queue * creatQueue()
22 {
23     struct queue * q = (struct queue * )malloc(sizeof(struct queue));
24     q->rear = q->front = NULL;
25 
26     return q;
27 }
28 int isEmpty(struct queue * q)
29 {
30     return NULL == q->front ? 1 : 0;
31 }
32 void enQueue(struct queue * q, int data)
33 {
34     struct node * new_node = creatNode(data);
35 
36     if(NULL == q->rear && NULL == q->front)
37     {
38         //q->rear和q->front和new_node 指向同一块地址。可以通过其中的任意一个来修改 new_node 里的值
39         q->rear = q->front = new_node;
40     }
41     else
42     {
43         //q->rear 修改了 next 值，q->front->next
44         q->rear->next = new_node;
45         q->rear = new_node;
46     }
47     printf("
%d enqueued", data);
48 }
49 struct node * deQueue(struct queue * q)
50 {
51     struct node * temp;
52     if(NULL == q->front)
53     {
54         printf("
Empty");
55         return ;
56     }
57     temp = q->front;
58     q->front = q->front->next;
59     //将元素全部删除完了
60     if(NULL == q->front)
61     {
62         q->rear = NULL;
63     }
64     return temp;
65 }
66 int main(void)
67 {
68     struct queue * q = creatQueue();
69     enQueue(q, 1);
70     enQueue(q, 2);
71     printf("
%d", deQueue(q)->data);
72     printf("
%d", deQueue(q)->data);
73     return 0;
74 }