争渡
1#ifndef _QUEUE_H_
2#define _QUEUE_H_
3#include <stdbool.h>
4typedef int Item;
5#define MAXQUEUE 10
6typedef struct node
7{
8 Item item;
9 struct node *next;
10} Node;
11
12typedef struct queue
13{
14 // 队列首项
15 Node *front;
16 // 队列尾项
17 Node *rear;
18 // 队列长度
19 int items;
20} Queue;
21// 初始化队列
22void InitializeQueue(Queue *pq);
23// 队列是否满了
24bool QueueIsFull(const Queue *pq);
25// 队列是否空了
26bool QueueIsEmpty(const Queue *pq);
27// 队列项数
28int QueueItemCount(const Queue *pq);
29// 入队
30bool EnQueue(Item item, Queue *pq);
31// 出队
32bool DeQueue(Item *pitem, Queue *pq);
33// free memory
34void EmptyQueue(Queue *pq);
35void showAll(Queue *pq);
36#endif
1#include <stdio.h>
2#include <stdlib.h>
3#include "queue.h"
4// 拷贝节点
5static void CopyToNode(Item item, Node *pn);
6// 拷贝项
7static void CopyToItem(Node *pn, Item *pi);
8// 初始化队列
9void InitializeQueue(Queue *pq)
10{
11 pq->front = pq->rear = NULL;
12 pq->items = 0;
13};
14// 队列是否满了
15bool QueueIsFull(const Queue *pq)
16{
17 return pq->items == MAXQUEUE;
18};
19// 队列是否空了
20bool QueueIsEmpty(const Queue *pq)
21{
22 return pq->items == 0;
23}
24// 队列项数
25int QueueItemCount(const Queue *pq)
26{
27 return pq->items;
28}
29// 入队
30bool EnQueue(Item item, Queue *pq)
31{
32 // 新建一个要插入队的节点
33 Node *pnew;
34 // 队列是否满了
35 if (QueueIsFull(pq))
36 {
37 return false;
38 }
39 // 为元素分配内存
40 pnew = (Node *)malloc(sizeof(Node));
41 // 是否分配好了内存
42 if (pnew == NULL)
43 {
44 return false;
45 }
46 // 节点赋值
47 CopyToNode(item, pnew);
48 // 下一个节点为null
49 pnew->next = NULL;
50 // 查看队列是否为空
51 if (QueueIsEmpty(pq))
52 {
53 // 如果为空的话,pq队列的首项为 pnew
54 pq->front = pnew;
55 }
56 else
57 {
58 // 否则插入尾项的下一个位置
59 pq->rear->next = pnew;
60 }
61 // 更新pq队列的尾项
62 pq->rear = pnew;
63 // 项 +1
64 pq->items++;
65 return true;
66}
67// 出队
68bool DeQueue(Item *pitem, Queue *pq)
69{
70 Node *pt;
71 // 是否为空队列
72 if (QueueIsEmpty(pq))
73 {
74 return false;
75 }
76 // pitem指向 队首的item
77 CopyToItem(pq->front, pitem);
78 // pt 指向 队首
79 pt = pq->front;
80 // 队首为下一个元素
81 pq->front = pq->front->next;
82 // 释放内存
83 free(pt);
84 // 项数-1
85 pq->items--;
86 if (pq->items == 0)
87 {
88 pq->rear = NULL;
89 }
90 return true;
91}
92// free memory
93void EmptyQueue(Queue *pq)
94{
95 Item dummy;
96 while (!QueueIsEmpty(pq))
97 {
98 DeQueue(&dummy, pq);
99 }
100}
101
102static void CopyToNode(Item item, Node *pn)
103{
104 pn->item = item;
105}
106static void CopyToItem(Node *pn, Item *pi)
107{
108 *pi = pn->item;
109}
110
1#include <stdio.h>
2#include "queue.h"
3
4int main(void)
5{
6 Queue line;
7 Item item;
8 char ch;
9 InitializeQueue(&line);
10 puts("Testing the queue interface ,Type a to add a value\n");
11 puts("type d to delete a value and type q to quit\n");
12 while ((ch = getchar()) != 'q')
13 {
14 switch (ch)
15 {
16 case 'a':
17 printf("Integer to add\n");
18 scanf("%d", &item);
19 if (!QueueIsFull(&line))
20 {
21 printf("Putting %d into queue\n", item);
22 EnQueue(item, &line);
23 }
24 else
25 {
26 puts("The queue is full\n");
27 }
28 break;
29 case 'd':
30 if (QueueIsEmpty(&line))
31 {
32 puts("Nothing to delete\n");
33 }
34 else
35 {
36 DeQueue(&item, &line);
37 printf("Removing %d from queue\n", item);
38 }
39 break;
40 default:
41 printf("Please enter %c %c %c\n", 'a', 'd', 'q');
42 break;
43 }
44 }
45 EmptyQueue(&line);
46 puts("Bye !\n");
47}