队列是一种操作受限的线性表，插入（入队）的一端为队尾，删除（出队）的一端是队头。队列每次入队的元素总是顺序出队，所是先进先出。

队列的基本运算：

• 置空队列
• 判断队空
• 入队
• 获取头元素
• 出队

队列的存储方式：顺序循序队列和链队列和循环链队列。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #define QueueSize 100
 5 
 6 typedef char DataType;
 7 typedef struct {
 8     DataType data[QueueSize];
 9     int front, rear;
10 }CirQueue;
11 /**
12 ** 置空队列 
13 **/
14 void InitQueue(CirQueue *Q) {
15     Q->front = Q->rear = 0; 
16 } 
17 
18 /**
19 **队列空 
20 **/
21 int QueueEmpty(CirQueue *Q) {
22     return Q->rear = Q->front;
23 }
24 
25 /**
26 **队列满 
27 **/ 
28 int QueueFull(CirQueue *Q) {
29     return (Q->rear + 1) % QueueSize == Q->front;
30 }
31 
32 /**
33 **入队列
34 **/
35 void EnQueue(CirQueue *Q, DataType x) {
36     if(QueueFull(Q)) {
37         printf("Queue overflow\n");
38     } else {
39         Q->data[Q->rear] = x;
40         Q->rear = (Q->rear + 1) % QueueSize;
41     }
42 } 
43 
44 /**
45 **取头元素 
46 **/
47 DataType GetFront(CirQueue *Q) {
48     if (QueueEmpty(Q)){
49         printf("Queue empty\n");
50         exit(0);
51     } else
52         return Q->data[Q->front];
53 }
54 /**
55 **出队列 
56 **/
57 DataType DeQueue(CirQueue *Q) {
58     DataType x;
59     if(QueueEmpty(Q)){
60         printf("Queue empty\n");
61         exit(0);
62     } else {
63         x = Q->data[Q->front];
64         Q->front = (Q->front + 1) % QueueSize;
65         return x;
66     }
67 }
68 
69 int main(void) {
70     CirQueue s;
71     CirQueue *Q = &s;
72     InitQueue(Q);
73     EnQueue(Q, 'h');
74     printf("%c\n", DeQueue(Q));
75     return 0;
76 }

View Code

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 typedef char DataType;
 5  
 6 typedef struct qnode{
 7     DataType data;
 8     struct qnode *next;
 9 }QueueNode; 
10 
11 typedef struct linkqueue{
12     QueueNode *front;
13     QueueNode *rear;
14 }LinkQueue;
15 
16 /**
17 **构造空队列
18 **/ 
19 void InitQueue(LinkQueue *Q) {
20     Q->front = (QueueNode *)malloc(sizeof(QueueNode));
21     Q->rear = Q->front;
22     Q->rear->next = NULL; 
23 } 
24 
25 /**
26 **判断队空 
27 **/
28 int QueueEmpty(LinkQueue *Q) {
29     return Q->front == Q->rear;
30 }
31 
32 /**
33 **入队列 
34 **/ 
35 void EnQueue(LinkQueue *Q, DataType x) {
36     QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));
37     p->data = x;
38     p->next = NULL;
39     Q->rear->next = p;
40     Q->rear = p; 
41 }
42 
43 /**
44 **取队头元素
45 **/
46 DataType GetFront(LinkQueue *Q) {
47     if (QueueEmpty(Q)) {
48         printf("Queue underflow\n");
49         exit(0);
50     } else {
51         return Q->front->next->data;
52     }
53 } 
54 
55 /**
56 **出队列
57 **/
58 DataType DeQueue(LinkQueue *Q) {
59     QueueNode *p;
60     if (QueueEmpty(Q)) {
61         printf("Queue underflow\n");
62         exit(0);
63     } else {
64         p = Q->front;
65         Q->front =  Q->front->next;
66         free(p);
67         return Q->front->data;
68     }
69 }
70 
71 int main(void) {
72     LinkQueue Q;
73     InitQueue(&Q);
74     EnQueue(&Q, 'h');
75     EnQueue(&Q, 'e');
76     DataType v = DeQueue(&Q);
77     printf("content:%c\n", v);
78     printf("content:%c\n", DeQueue(&Q));
79     return 0;
80 } 
81  

View Code