c中queue的用法

学习啦在线学习网 　　下面小编就跟你们详细介绍下c中queue的用法的用法，希望对你们有用。

　　c中queue的用法的用法如下：

　　Model

学习啦在线学习网 　　------------------------------------------------------------------------------------------------------------------------

　　队列也是限制插入和删除位置的表.

　　主要操作是enqueue和dequeue操作.

　　enqueue:入队操作.在表的队尾(rear)插入一个元素.

　　dequeue:出队操作.删除表的队首(front)元素.

　　本文使用循环数组实现GenericQueue.需要指定capacity.缺点是超出容量,无法动态增长.当然,可以仿照list的方式克服这个问题.

学习啦在线学习网 　　完整代码详见我的github(http://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]处.