c中queue的用法
- 格式：docx
- 大小：17.92 KB
- 文档页数：8
c中queue的用法
下面小编就跟你们详细介绍下c中queue的用法的用法，希望对你们有用。
c中queue的用法的用法如下：
Model
------------------------------------------------------------------------------------------------------------------------
队列也是限制插入和删除位置的表.
主要操作是enqueue和dequeue操作.
enqueue:入队操作.在表的队尾(rear)插入一个元素.
dequeue:出队操作.删除表的队首(front)元素.
本文使用循环数组实现GenericQueue.需要指定capacity.缺点是超出容量,无法动态增长.当然,可以仿照list的方式克服这个问题.
完整代码详见我的github(https:///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. }
