抽象数据类型之队列ADT接口包

mingcxx

这个是队列ADT的接口包了，只是一些简单的功能。以后需要什么再向里面添加就行。

1. //queue.h -- 队列接口头文件
   
2. 
   
3. #ifndef _QUEUE_H_
   
4. #define _QUEUE_H_
   
5. 
   
6. #include <stdbool.h>
   
7. 
   
8. /*在这里键入Item的类型定义*/
   
9. //例如
   
10. typedef int Item;
    
11. 
    
12. #define MAXQUEUE 10                //队列的最大长度
    
13. 
    
14. typedef        struct node
    
15. {
    
16.         Item item;
    
17.         struct node * next;
    
18. } Node;
    
19. 
    
20. typedef struct queue
    
21. {
    
22.         Node * front;                //指向队列首的指针
    
23.         Node * rear;                //指向队列尾的指针
    
24.         int items;                        //队列中项目的个数
    
25. } Queue;
    
26. 
    
27. /*操作：初始化队列
    
28. 操作前：pq指向一个队列
    
29. 操作后：该队列被初始化为空队列*/
    
30. void InitializeQueue(Queue * pq);
    
31. 
    
32. 
    
33. /*操作：检查队列是否为空
    
34. 操作前：pq指向一个已初始化的队列
    
35. 操作后：如果队列为空，则返回true；
    
36. 否则返回false*/
    
37. bool QueueIsEmpty(const Queue * pq);
    
38. 
    
39. 
    
40. /*操作：检查队列是否已满
    
41. 操作前：pq指向一个已初始化的队列
    
42. 操作后：如果队列已满，则返回true；
    
43. 否则返回false*/
    
44. bool QueueIsFull(const Queue * pq);
    
45. 
    
46. 
    
47. /*操作：确定队列中项目的个数
    
48. 操作前：pq指向一个已初始化的队列
    
49. 操作后：返回一个队列中项目的个数*/
    
50. int QueueItemCount(const Queue * pq);
    
51. 
    
52. 
    
53. /*操作：向队列尾端添加项目
    
54. 操作前：pq指向一个已初始化的队列
    
55. item是要添加到队列尾的项目
    
56. 操作后：如果队列未满，则将该项目
    
57. 添加到队列尾，函数返回true；否则
    
58. 返回false*/
    
59. bool EnQueue(Item item, Queue * pq);
    
60. 
    
61. 
    
62. /*操作：从队列首端删除项目
    
63. 操作前：pq指向一个已初始化的队列
    
64. 操作后：如果队列非空，队列首端的
    
65. 项目被复制到*pitem,并从队列中删
    
66. 除，函数返回true；如果这个操作使
    
67. 队列为空，把队列重置为空队列
    
68. 如果队列开始时为空，不改变队列，
    
69. 函数返回false*/
    
70. bool DeQueue(Item * pitem, Queue * pq);
    
71. 
    
72. 
    
73. /*操作：清空队列
    
74. 操作前：pq指向一个已经初始化的队列
    
75. 操作后：队列被清空*/
    
76. void EmptyTheQueue(Queue * pq);
    
77. 
    
78. 
    
79. #endif // !_QUEUE_H_

复制代码

1. //queue.c -- 队列类型的实现文件
   
2. 
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. #include "queue.h"
   
6. 
   
7. 
   
8. /*局部函数*/
   
9. static void CopyToNode(Item item, Node * pnode);
   
10. static void CopyToItem(Node * pnode, Item * pitem);
    
11. 
    
12. void InitializeQueue(Queue * pq)
    
13. {
    
14.         pq->front = pq->rear = NULL;
    
15.         pq->items = 0;
    
16. }
    
17. 
    
18. bool QueueIsEmpty(const Queue * pq)
    
19. {
    
20.         return pq->items == 0;
    
21. }
    
22. 
    
23. bool QueueIsFull(const Queue * pq)
    
24. {
    
25.         return pq->items == MAXQUEUE;
    
26. }
    
27. 
    
28. int QueueItemCount(const Queue * pq)
    
29. {
    
30.         return pq->items;
    
31. }
    
32. 
    
33. bool EnQueue(Item item, Queue * pq)
    
34. {
    
35.         Node * pnew;
    
36. 
    
37.         if (QueueIsFull(pq))
    
38.         {
    
39.                 return false;
    
40.         }
    
41. 
    
42.         pnew = (Node *)malloc(sizeof(Node));
    
43.         if (pnew == NULL)
    
44.         {
    
45.                 fprintf(stderr, "Unable to allocate memory.\n");
    
46.                 exit(EXIT_FAILURE);
    
47.         }
    
48. 
    
49.         CopyToNode(item, pnew);
    
50.         pnew->next = NULL;
    
51.         if (QueueIsEmpty(pq))
    
52.         {
    
53.                 pq->front = pnew;                        //项目位于队列首端
    
54.         }
    
55.         else
    
56.         {
    
57.                 pq->rear->next = pnew;                //项目链接到队列尾端
    
58.         }
    
59.         pq->rear = pnew;                                //尾指针指向尾节点
    
60.         pq->items++;                                        //项目数 + 1
    
61. 
    
62.         return true;
    
63. }
    
64. 
    
65. bool DeQueue(Item * pitem, Queue * pq)
    
66. {
    
67.         Node * pt;
    
68. 
    
69.         if (QueueIsEmpty(pq))
    
70.         {
    
71.                 return false;
    
72.         }
    
73. 
    
74.         CopyToItem(pq->front, pitem);
    
75.         pt = pq->front;
    
76.         pq->front = pq->front->next;
    
77.         free(pt);
    
78.         pq->items--;
    
79.         if (pq->items == 0)
    
80.         {
    
81.                 pq->rear = NULL;
    
82.         }
    
83.        
    
84.         return true;
    
85. }
    
86. 
    
87. void EmptyTheQueue(Queue * pq)
    
88. {
    
89.         Item item;
    
90. 
    
91.         while (!QueueIsEmpty(pq))
    
92.         {
    
93.                 DeQueue(&item, pq);
    
94.         }
    
95. }
    
96. 
    
97. //局部函数定义
    
98. static void CopyToNode(Item item, Node * pnode)
    
99. {
    
100.         pnode->item = item;
     
101. }
     
102. 
     
103. static void CopyToItem(Node * pnode, Item * pitem)
     
104. {
     
105.         *pitem = pnode->item;
     
106. }

复制代码