[队列]简单的队列操作

本文摘抄于《C嵌入式编程设计模式》

1. 头文件部分：Queue.h

 1 #ifndef __QUEUE_H_
 2 #define __QUEUE_H_
 3 
 4 #define QUEUE_SIZE     10
 5 
 6 /* class queue */
 7 typedef struct Queue queue;
 8 struct Queue
 9 {
10     int buffer[QUEUE_SIZE];
11     int head;
12     int size;
13     int tail;
14     int (*isFull)(Queue *const me);
15     int (*isEmpty)(Queue *const me);
16     int (*getSize)(Queue *const me);
17     void (*insert)(Queue *const me, int k);
18     int (*remove)(Queue *const me);    
19 };
20 
21 /* Constructors and destructors */
22 void Queue_init(Queue *const me, int (*isFull)(Queue *const me),
23                 int (*isEmpty)(Queue *const me),
24                 int (*getSize)(Queue *const me),
25                 void (*insert)(Queue *const me, int k),
26                 int (*remove)(Queue *const me));
27 void Queue_Cleanup(Queue *const me);
28 /* Operaters */
29 int Queue_isFull(Queue *const me);
30 int Queue_isEmpty(Queue *const me);
31 int Queue_getSize(Queue *const me);
32 void Queue_insert(Queue *const me, int k);s
33 int Queue_remove(Queue *const);
34 
35 Queue *Queue_Create(void);
36 void Queue_Destroy(Queue *const me);
37 
38 #endif

2. 源文件实现部分：queue.c

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "Queue.h"
 4 
 5 /* init struct */
 6 void Queue_init(Queue *const me, int (*isFullFunction)(Queue *const me),
 7                 int (*isEmptyFunction)(Queue *const me),
 8                 int (*getSizeFunction)(Queue *const me),
 9                 void (*insertFunction)(Queue *const me, int k),
10                 int (*removeFunction)(Queue *const me))
11 {
12     me->head = 0;
13     me->size = 0;
14     me->tail = 0;
15 
16     me->isFull = isFullFunction;
17     me->isEmpty = isEmptyFunction;
18     me->getSize = getSizeFunction;
19     me->insert = insertFunction;
20     me->remove = removeFunction;
21 }
22 /* operation clean up */
23 void Queue_Cleanup(Queue * const me)
24 {
25     //TODO:
26 }
27 /* operation is Full */
28 int Queue_isFull(Queue * const me)
29 {
30     return (me->head+1)%QUEUE_SIZE == me->tail;
31 }
32 /* operation isEmpty */
33 int Queue_isEmpty(Queue * const me)
34 {
35     return (me->head == me->tail);
36 }
37 /* operation getSize */
38 int Queue_getSize(Queue * const me)
39 {
40     return me->size;
41 }    
42 /* operation insert */
43 void Queue_insert(Queue * const me,int k)
44 {
45     if(!me->isFull(me))
46     {
47         me->buffer[me->head] = k;
48         me->head = (me->head+1)%QUEUE_SIZE;
49         ++me->size;
50     }
51 }
52 /* operation remove */
53 int Queue_remove(Queue *const me)
54 {
55     int value = -9999;
56     if(!me->isEmpty(me))
57     {
58         value = me->buffer[me->tail];
59         me->tail = (me->tail+1)%QUEUE_SIZE;
60         --me->size;
61     }
62     return value;
63 }
64 /* queue create */
65 Queue *Queue_Create(void)
66 {
67     Queue *me = (Queue*)malloc(sizeof(Queue));
68     if(me!=NULL)
69     {
70         Queue_init(me,Queue_isFull,Queue_isEmpty,Queue_getSize,Queue_insert,Queue_remove);
71     }
72     return me;
73 }
74 /* queue remove */
75 void Queue_remove(Queue *const me)
76 {
77     if(me!= NULL)
78     {
79         Queue_Cleanup(me);
80     }
81     free(me);
82 }

　3. 队列测试代码：TestQueue.c

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "Queue.h"
 4 
 5 int main(void)
 6 {
 7     int j,k,h,t;
 8 
 9     /* test normal queue */
10     Queue *myQ;
11     myQ = Queue_Create();
12     k = 1000;
13 
14     for(j = 0; j < QUEUE_SIZE; j++)
15     {
16         h = myQ->head;
17         myQ->insert(myQ, k);
18         printf("inserting %d at position %d, size=%d
", k--, h, myQ->getSize(myQ));
19     }
20     printf("Inserting %d elements
", myQ->getSize(myQ));
21     for(j = 0;j < QUEUE_SIZE; j++)
22     {
23         t = myQ->tail;
24         k = myQ->getSize(myQ);
25         printf("Removing %d at position %d, size=%d
", k, t, myQ->getSize(myQ));        
26     }
27 
28     printf("last item removed %d
", k);
29     printf("Current queue size %d
", myQ->getSize(myQ));
30     puts("Queue test program");
31     
32     return EXIT_SUCCESS;
33