七考網(wǎng)
2023-11-05 09:20:09來源：互聯(lián)網(wǎng)
摘要：下面小編就跟你們詳細(xì)介紹下c中queue的用法的用法，希望對你們有用。c中queue的用法的用法如下：Model--------------------------------------
(資料圖片)
c中queue的用法的用法如下：
Model
------------------------------------------------------------------------------------------------------------------------
隊列也是限制插入和刪除位置的表.
主要操作是enqueue和dequeue操作.
enqueue:入隊操作.在表的隊尾(rear)插入一個元素.
dequeue:出隊操作.刪除表的隊首(front)元素.
本文使用循環(huán)數(shù)組實現(xiàn)GenericQueue.需要指定capacity.缺點是超出容量,無法動態(tài)增長.當(dāng)然,可以仿照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.}
分析
----------------
本文使用循環(huán)數(shù)組實現(xiàn)GenericQueue.需要指定capacity.既然是循環(huán)數(shù)組,就是圍成一個圈.也就插入第一個元素沒有必要非要放在0處啦.
初始狀態(tài):
{
que->size = 0;
que->front = 1;
que->rear = 0;
}
說明這樣第一次enqueue操作放在array[1]處,當(dāng)然:這不是必須的,取決于你想放在那里.
#define mxx
{
que->size = 0;
que->front =m+1;
que->rear = m;
}
就放在array[m+1]處.
一級建造師 二級建造師 消防工程師 消防設(shè)施操作員 BIM 造價工程師 環(huán)評師 監(jiān)理工程師 咨詢工程師 安全工程師 建筑九大員 公路水運檢測 通信工程 智慧消防工程師 裝配工程師 一級注冊建筑師 二級注冊建筑師 注冊電氣工程師 智慧建造工程師 房地產(chǎn)估價師 應(yīng)急救援員 EPC工程總承包 PLC智能制造 碳排放管理師 雅思 托福 GRE 托業(yè) SAT GMAT A-Level ACT AP課程 OSSD 多鄰國英語 考研英語 英語四六級 商務(wù)英語 青少兒英語 IB英語 劍橋英語 職場英語 提升英語 AEAS 英語口語 出國英語 初高中英語 學(xué)生英語 成人英語 公共英語 詞庫 經(jīng)濟師 初級會計師 中級會計師 注冊會計師 基金從業(yè) 證券從業(yè) 薪稅師 銀行從業(yè) CMA ACCA 會計實訓(xùn) 稅務(wù)師 CFA 企業(yè)合規(guī)師 審計師 FRM 高級會計師 會計就業(yè) 期貨從業(yè) CQF 真賬實操技能 葡萄牙語 日語 德語 法語 韓語 西班牙 意大利 高考小語種 粵語 泰語 俄語 阿拉伯語 電商視覺設(shè)計 影視后期 剪輯包裝 游戲設(shè)計 游戲程序 UI設(shè)計 室內(nèi)設(shè)計 UXD全鏈路 平面設(shè)計 CAD設(shè)計制圖 商業(yè)空間設(shè)計
