链式队列的实现

queue.h

 1 #ifndef QUEUE_H
 2 #define QUEUE_H
 3 
 4 #include<stdio.h>
 5 #include<stdlib.h>
 6 #include<time.h>
 7 
 8 //node
 9 typedef struct QueueNode
10 {
11     int data;
12     struct QueueNode* next;
13 }NODE;
14 
15 //queue
16 typedef struct
17 {
18     NODE *front;
19     NODE *rear;
20 }LinkQueue;
21 
22 //初始化
23 void init(LinkQueue *q);
24 //创建队列
25 void create(LinkQueue *q);
26 //添加一个元素至队尾
27 void append(LinkQueue *q, int val);
28 //从队头删除一个元素
29 void serve(LinkQueue *q, int *val);
30 //获取队首的元素值
31 void top(LinkQueue *q, int *val);
32 
33 //判断队列是否为空
34 int isEmpty(LinkQueue *q);
35 //获取队列的长度
36 int length(LinkQueue *q);
37 //打印队列
38 void print(LinkQueue *q);
39 //清除队列
40 void clear(LinkQueue *q);
41 
42 
43 #endif

queue.c

  1 #include "queue.h"
  2 
  3 void init(LinkQueue *q)
  4 {
  5     q->front = q->rear = (NODE*)malloc(sizeof(NODE));
  6     q->front->next = NULL;
  7 }
  8 
  9 void create(LinkQueue *q)
 10 {
 11     init(q);
 12     int index;
 13     for(index = 0; index < 15; index++)
 14         append(q,rand() % 100);
 15 }
 16 
 17 void append(LinkQueue *q, int val)
 18 {
 19     NODE *newNode = (NODE*)malloc(sizeof(NODE));
 20     newNode->data = val;
 21     if(newNode)
 22     {
 23         newNode->next = NULL;
 24         q->rear->next = newNode;
 25         q->rear = newNode;
 26     }
 27 }
 28 
 29 void serve(LinkQueue *q, int *val)
 30 {
 31     if(q->front == q->rear)
 32     {
 33         printf("The queue is empty!
");
 34         return;
 35     }
 36     NODE *oldNode = q->front->next;
 37     *val = oldNode->data;
 38     //只有一个元素,队列置空
 39     if(q->front->next == q->rear)
 40         q->rear = q->front;
 41     q->front->next = oldNode->next;
 42     free(oldNode);
 43 }
 44 
 45 int isEmpty(LinkQueue *q)
 46 {
 47     if(q->front == q->rear)
 48         return 1;
 49     return 0;
 50 }
 51 
 52 int length(LinkQueue *q)
 53 {
 54     int len = 0;
 55     NODE *pcur = q->front;
 56     while(pcur != q->rear)
 57     {
 58         len++;
 59         pcur = pcur->next;
 60     }
 61     return len;
 62 }
 63 
 64 void clear(LinkQueue *q)
 65 {
 66     NODE *ptem, *pcur;
 67     pcur = q->front->next;
 68     while(pcur)
 69     {
 70         ptem = pcur;
 71         pcur = pcur->next;
 72         free(ptem);
 73     }
 74     //删去头结点
 75     pcur = q->front;
 76     q->front = q->rear = NULL;
 77     free(pcur);
 78 }
 79 
 80 void print(LinkQueue *q)
 81 {
 82     if(q->front == q->rear)
 83     {
 84         printf("The queue is empty!
");
 85         return;
 86     }
 87     NODE *pcur = q->front->next;
 88     while(pcur)
 89     {
 90         printf("->%2d",pcur->data);
 91         pcur = pcur->next;
 92     }
 93     printf("
");
 94 }
 95 
 96 void top(LinkQueue *q, int *val)
 97 {
 98     if(q->front == q->rear)
 99     {
100         printf("The queue si empty!
");
101         return;
102     }
103     *val = q->front->next->data;
104 }

main.c

 1 #include "queue.h"
 2 
 3 int main()
 4 {
 5     LinkQueue q;
 6     create(&q);
 7 
 8     int len = length(&q);
 9     int index, val;
10 
11     printf("依次出队:
");
12     for(index = 0; index < len; index++)
13     {
14         serve(&q,&val);
15         printf("->%2d",val);
16     }
17     printf("
");
18     clear(&q);
19 
20     return 0;
21 }