c中queue的用法
【计算机英语】 2016-03-20本文已影响
人
下面小编就跟你们详细介绍下c中queue的用法的用法,希望对你们有用。
c中queue的用法的用法如下:
Model
------------------------------------------------------------------------------------------------------------------------
队列也是限制插入和删除位置的表.
主要操作是enqueue和dequeue操作.
enqueue:入队操作.在表的队尾(rear)插入一个元素.
dequeue:出队操作.删除表的队首(front)元素.
本文使用循环数组实现GenericQueue.需要指定capacity.缺点是超出容量,无法动态增长.当然,可以仿照list的方式克服这个问题.
完整代码详见我的github(https://github.com/gnudennis/ds_c)(genric-queue.h generic-queue.c generic-queue-test.c)
核心代码
------------------------------------------------------------------------------------------------------------------------
0. Generic Queue定义
[cpp] view plain copy
01.typedef void *ElementAddr;
02.typedef void (*PfCbFree)(ElementAddr);
03.
04.typedef struct QueueRecord
05.{
06. ? ? ? ?ElementAddr *array;
07. ? ? ? ?int ? ? capacity;
08. ? ? ? ?int ? ? elemsize;
09. ? ? ? ?int ? ? front;
10. ? ? ? ?int ? ? rear;
11. ? ? ? ?int ? ? size;
12. ? ? ? ?PfCbFree ? ?freefn;
13.} *Queue;
1. API
[cpp] view plain copy
01./* Create a new queue */
02.Queue queue_create(int elemsize, int capacity, PfCbFree freefn);
03.
04./* Dispose the queue */
05.void queue_dispose(Queue que);
06.
07./* Make the give queue empty */
08.void queue_make_empty(Queue que);
09.
10./* Return true if the queue is empty */
11.int queue_is_empty(Queue que);
12.
13./* Return true if the queue is full */
14.int queue_is_full(Queue que);
15.
16./* Insert a new element onto queue */
17.void queue_enqueue(Queue que, ElementAddr elemaddr);
18.
19./* Delete the front element off the queue */
20.void queue_dequeue(Queue que);
21.
22./* Fetch the front element from the queue */
23.void queue_front(Queue que, ElementAddr elemaddr);
24.
25./* Fetch and Delete the front element from the queue */
26.void queue_front_and_dequeue(Queue que, ElementAddr elemaddr);
2.Implementation
[cpp] view plain copy
01./* Create a new queue with capacity */
02.Queue
03.queue_create(int elemsize, int capacity, PfCbFree freefn)
04.{
05. ? ? ? ?Queue que;
06.
07. ? ? ? ?que = malloc(sizeof(struct QueueRecord));
08. ? ? ? ?if ( que == NULL ) {
09. ? ? ? ? ? ? ? ?fprintf(stderr, "Out of memory\n");
10. ? ? ? ? ? ? ? ?exit(1);
11. ? ? ? ?}
12.
13. ? ? ? ?que->elemsize = elemsize;
14. ? ? ? ?que->capacity = capacity > MIN_QUEUE_SIZE ? capacity : MIN_QUEUE_SIZE;
15.
16. ? ? ? ?que->array = malloc(elemsize * que->capacity);
17. ? ? ? ?if ( que->array == NULL ) {
18. ? ? ? ? ? ? ? ?fprintf(stderr, "Out of memory\n");
19. ? ? ? ? ? ? ? ?exit(1);
20. ? ? ? ?}
21. ? ? ? ?que->front = 1;
22. ? ? ? ?que->rear = 0;
23. ? ? ? ?que->size = 0;
24. ? ? ? ?que->freefn = freefn;
25.
26. ? ? ? ?return que;
27.}
28.
29./* Dispose the queue */
30.void
31.queue_dispose(Queue que)
32.{
33. ? ? ? ?if (que != NULL) {
34. ? ? ? ? ? ? ? ?queue_make_empty(que);
35. ? ? ? ? ? ? ? ?free(que->array);
36. ? ? ? ? ? ? ? ?free(que);
37. ? ? ? ?}
38.}
39.
40./* Make the give queue empty */
41.void
42.queue_make_empty(Queue que)
43.{
44. ? ? ? ?if ( que->freefn ) {
45. ? ? ? ? ? ? ? ?int i;
46. ? ? ? ? ? ? ? ?for ( i = 0; i < que->size; ++i) {
47. ? ? ? ? ? ? ? ? ? ? ? ?free((char *)que->array +
48. ? ? ? ? ? ? ? ? ? ? ? ? ? ? que->elemsize * i);
49. ? ? ? ? ? ? ? ?}
50. ? ? ? ?}
51. ? ? ? ?que->size = 0;
52. ? ? ? ?que->front = 1;
53. ? ? ? ?que->rear = 0;
54.}
55.
56./* Return true if the queue is empty */
57.int
58.queue_is_empty(Queue que)
59.{
60. ? ? ? ?return que->size == 0;
61.}
62.
63./* Return true if the queue is full */
64.int
65.queue_is_full(Queue que)
66.{
67. ? ? ? ?return que->size == que->capacity;
68.}
69.
70.static int
71.successor(Queue que, int index)
72.{
73. ? ? ? ?if ( ++index == que->capacity)
74. ? ? ? ? ? ? ? ?index = 0;
75. ? ? ? ?return index;
76.}
77.
78./* Insert a new element onto queue(rear) */
79.void
80.queue_enqueue(Queue que, ElementAddr elemaddr)
81.{
82. ? ? ? ?void *target;
83.
84. ? ? ? ?if ( queue_is_full(que) ) {
85. ? ? ? ? ? ? ? ?fprintf(stderr, "Full queue\n");
86. ? ? ? ? ? ? ? ?exit(1);
87. ? ? ? ?}
88. ? ? ? ?que->rear = successor(que, que->rear);
89. ? ? ? ?target = (char *)que->array + que->elemsize * que->rear;
90. ? ? ? ?memcpy(target, elemaddr, que->elemsize);
91. ? ? ? ?que->size++;
92.}
93.
94./* Delete the front element off the queue */
95.void
96.queue_dequeue(Queue que)
97.{
98. ? ? ? ?if ( queue_is_empty(que) ) {
99. ? ? ? ? ? ? ? ?fprintf(stderr, "Empty queue\n");
100. ? ? ? ? ? ? ? ?exit(1);
101. ? ? ? ?}
102. ? ? ? ?if ( que->freefn ) {
103. ? ? ? ? ? ? ? ?void *target = (char *)que->array +
104. ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? que->front * que->elemsize;
105. ? ? ? ? ? ? ? ?que->freefn(target);
106. ? ? ? ?}
107. ? ? ? ?que->size--;
108. ? ? ? ?que->front = successor(que, que->front);
109.}
110.
111./* Fetch the front element from the queue */
112.void
113.queue_front(Queue que, ElementAddr elemaddr)
114.{
115. ? ? ? ?void *target = (char *)que->array +
116. ? ? ? ? ? ? ? ? ? ? ? que->front * que->elemsize;
117. ? ? ? ?memcpy(elemaddr, target, que->elemsize);
118.}
119.
120./* Fetch and Delete the front element from the queue */
121.void
122.queue_front_and_dequeue(Queue que, ElementAddr elemaddr)
123.{
124. ? ? ? ?void *target;
125.
126. ? ? ? ?if ( queue_is_empty(que) ) {
127. ? ? ? ? ? ? ? ?fprintf(stderr, "Empty queue\n");
128. ? ? ? ? ? ? ? ?exit(1);
129. ? ? ? ?}
130.
131. ? ? ? ?target = (char *)que->array +
132. ? ? ? ? ? ? ? ? ? ? ? que->front * que->elemsize;
133. ? ? ? ?memcpy(elemaddr, target, que->elemsize);
134.
135. ? ? ? ?que->size--;
136. ? ? ? ?que->front = successor(que, que->front);
137.}
分析
----------------
本文使用循环数组实现GenericQueue.需要指定capacity.既然是循环数组,就是围成一个圈.也就插入第一个元素没有必要非要放在0处啦.
初始状态:
{
que->size = 0;
que->front = 1;
que->rear = 0;
}
说明这样第一次enqueue操作放在array[1]处,当然:这不是必须的,取决于你想放在那里.
#define mxx
{
que->size = 0;
que->front =m+1;
que->rear = m;
}
就放在array[m+1]处.
[c中queue的用法]相关的文章
【计算机英语】图文推荐
网友评论
- 上一篇:c中include的用法
- 下一篇:c中delete的用法