c中queue的用法
2023-11-05 09:20:09来源：互联网
摘要：下面小编就跟你们详细介绍下c中queue的用法的用法，希望对你们有用。c中queue的用法的用法如下：Model--------------------------------------
(资料图片)
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]处.
