c中queue的用法

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

　　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]处.