c中queue的用法
下面小編就跟你們?cè)敿?xì)介紹下c中queue的用法的用法，希望對(duì)你們有用。
c中queue的用法的用法如下：
Model
------------------------------------------------------------------------------------------------------------------------
隊(duì)列也是限制插入和刪除位置的表.
主要操作是enqueue和dequeue操作.
enqueue:入隊(duì)操作.在表的隊(duì)尾(rear)插入一個(gè)元素.
dequeue:出隊(duì)操作.刪除表的隊(duì)首(front)元素.
本文使用循環(huán)數(shù)組實(shí)現(xiàn)GenericQueue.需要指定capacity.缺點(diǎn)是超出容量,無(wú)法動(dòng)態(tài)增長(zhǎng).當(dāng)然,可以仿照l(shuí)ist的方式克服這個(gè)問(wèn)題.
完整代碼詳見(jiàn)我的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.}
分析
----------------
本文使用循環(huán)數(shù)組實(shí)現(xiàn)GenericQueue.需要指定capacity.既然是循環(huán)數(shù)組,就是圍成一個(gè)圈.也就插入第一個(gè)元素沒(méi)有必要非要放在0處啦.
初始狀態(tài):
{
que->size = 0;
que->front = 1;
que->rear = 0;
}
說(shuō)明這樣第一次enqueue操作放在array[1]處,當(dāng)然:這不是必須的,取決于你想放在那里.
#define mxx
{
que->size = 0;
que->front =m+1;
que->rear = m;
}
就放在array[m+1]處.
c中queue的用法
上一篇：c中out的用法
下一篇：c中random的用法
