007-队列

moc

1、基本概念
队列（queue）是一种 特殊的线性表；
队列仅在线性表的两端进行操作；
队头（Front）：取出数据元素的一端；
队尾（Rear）:   插入数据元素的一端。
队列不允许在中间位置插入元素或其他操作。
        队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。是一种先进先出的线性表（FIFO）.

常用操作：
        创建队列；
        销毁队列；
        清空队列；
        进队列；
        出队列；
        获取队头元素；
        获取队列的长度。
2、队列的线性存储
      同样由于队列是一种特殊的线性表，其实现也是可以通过线性表来完成的。
通过线性表的顺序存储来实现队列的顺序 存储。

1. // 创建一个队列  相当于 创建一个线性表
   
2. SeqQueue* SeqQueue_Create(int capacity)
   
3. {
   
4.         return SeqList_Create(capacity);
   
5. }
   
6. 
   
7. // 销毁一个队列  相当于 销毁一个线性表
   
8. void SeqQueue_Destroy(SeqQueue* queue)
   
9. {
   
10.         SeqList_Destroy(queue);
    
11. }
    
12. 
    
13. // 清空一个队列  相当于 清空一个线性表
    
14. void SeqQueue_Clear(SeqQueue* queue)
    
15. {
    
16.         SeqList_Clear(queue);
    
17. }
    
18. 
    
19. // 入队  相当于 向线性表添加一个元素
    
20. // 头插、尾插都可以，这里选择尾插法
    
21. int SeqQueue_Append(SeqQueue* queue, void* item)
    
22. {
    
23.         return SeqList_Insert(queue, item, SeqQueue_Length(queue));
    
24. }
    
25. 
    
26. // 出队 相当于 删除链表头部元素
    
27. void* SeqQueue_Retrieve(SeqQueue* queue)
    
28. {
    
29.         return SeqList_Delete(queue, 0);
    
30. }
    
31. 
    
32. // 获取队列头部元素 相当于 获取线性表头部元素
    
33. void* SeqQueue_Header(SeqQueue* queue)
    
34. {
    
35.         return SeqList_Get(queue, 0);
    
36. }
    
37. 
    
38. // 获取队列长度  相当于 获取线性表长度
    
39. int SeqQueue_Length(SeqQueue* queue)
    
40. {
    
41.         return SeqList_Length(queue);
    
42. }
    
43. 
    
44. // 获取队列容量  相当于 获取线性表容量
    
45. int SeqQueue_Capacity(SeqQueue* queue)
    
46. {
    
47.         return SeqList_Capacity(queue);
    
48. }

复制代码

3、队列的链式存储
和栈类似，队列的链式存储同样涉及到  ① 队列的业务结点向线性表业务结点的转换    ② 结点的生命周期的管理。

1. // 队列也是一种特殊的线性表
   
2. // 队列的业务结点的数据结构
   
3. typedef struct _tag_LinkQueueNode
   
4. {
   
5.         LinkListNode node;
   
6.         void* item;
   
7. }TLinkQueueNode;
   
8. 
   
9. 
   
10. 
    
11. // 创建一个队列  相当于 创建一个线性表
    
12. LinkQueue* LinkQueue_Create()
    
13. {
    
14.         return LinkList_Create();
    
15. }
    
16. 
    
17. // 销毁一个队列  相当于 销毁一个线性表
    
18. // 结点的内存管理
    
19. void LinkQueue_Destroy(LinkQueue* queue)
    
20. {
    
21.         LinkQueue_Clear(queue);
    
22.         LinkList_Destroy(queue);
    
23. }
    
24. 
    
25. 
    
26. // 清空一个队列  需要把队列里的每个元素取出来  释放掉
    
27. void LinkQueue_Clear(LinkQueue* queue)
    
28. {
    
29.         while (LinkQueue_Length(queue) > 0)
    
30.         {
    
31.                 LinkQueue_Retrieve(queue);
    
32.         }
    
33.         LinkList_Clear(queue);
    
34. }
    
35. 
    
36. 
    
37. // 入队  相当于 向线性表添加一个元素
    
38. // 头插、尾插都可以，这里选择尾插法
    
39. int LinkQueue_Append(LinkQueue* queue, void* item)
    
40. {
    
41.         int ret = 0;
    
42.         TLinkQueueNode *tmp = NULL;
    
43.         tmp = (TLinkQueueNode*)malloc(sizeof(TLinkQueueNode));
    
44.         if (tmp == NULL)
    
45.         {
    
46.                 ret = -1;
    
47.                 printf("Fun LinkQueue_Append() malloc error:%d", ret);
    
48.                 return ret;
    
49.         }
    
50.         memset(tmp, 0, sizeof(TLinkQueueNode));
    
51.         tmp->item = item;
    
52.         // 需要把队列的业务结点 转换为 线性表的业务结点
    
53.         ret = LinkList_Insert(queue, (LinkListNode*)tmp, LinkList_Length(queue));
    
54.         if (ret != 0)
    
55.         {
    
56.                 printf("Fun LinkList_Insert() error: %d\n", ret);
    
57.                 if (tmp != NULL)
    
58.                 {
    
59.                         free(tmp);
    
60.                         tmp = NULL;
    
61.                 }
    
62.         }
    
63.         return ret;
    
64. }
    
65. 
    
66. // 从队列中删除一个元素 相当于  从线性表中删除一个元素
    
67. void* LinkQueue_Retrieve(LinkQueue* queue)
    
68. {
    
69.         TLinkQueueNode *tmp = NULL;
    
70.         void                   *ret = NULL;
    
71.         tmp = (TLinkQueueNode*)LinkList_Delete(queue, 0);
    
72.         if (tmp == NULL)
    
73.         {
    
74.                 printf("Fun LinkList_Delete error\n");
    
75.                 return NULL;
    
76.         }
    
77.         ret = tmp->item;
    
78.         if (tmp != NULL)
    
79.         {
    
80.                 free(tmp);
    
81.         }
    
82.         return ret;
    
83. }
    
84. 
    
85. // 获取队列中头部元素 相当于  获取线性表的头部元素
    
86. void* LinkQueue_Header(LinkQueue* queue)
    
87. {
    
88.         TLinkQueueNode *tmp = NULL;
    
89.         void                   *ret = NULL;
    
90.         tmp = LinkList_Get(queue, 0);
    
91.         if (tmp == NULL)
    
92.         {
    
93.                 printf("func LinkList_Get() reeor\n");
    
94.                 return NULL;
    
95.         }
    
96.         return tmp->item;
    
97. }
    
98. 
    
99. // 求队列的长度 相当于 求线性表的长度
    
100. int LinkQueue_Length(LinkQueue* queue)
     
101. {
     
102.         return LinkList_Length(queue);
     
103. }

复制代码

完整代码： 队列的顺序存储.zip (2.72 KB, 下载次数: 5)

2018-9-26 23:01 上传

点击文件名下载附件
队列的顺序存储

                 队列的链式存储.zip (2.98 KB, 下载次数: 6)

2018-9-26 23:01 上传

点击文件名下载附件
队列的链式存储