【转】环形队列理论（C语言）

原文链接：http://blog.sina.com.cn/s/blog_8b200d440100xsug.html

环形队列是在实际编程极为有用的数据结构,它有如下特点。

它是一个首尾相连的FIFO的数据结构，采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。

因为有简单高效的原因，甚至在硬件都实现了环形队列.

环形队列广泛用于网络数据收发，和不同程序间数据交换（比如内核与应用程序大量交换数据,从硬件接收大量数据）均使用了环形队列.

一.环形队列实现原理

------------------------------------------------------------

内存上没有环形的结构，因此环形队列实上是数组的线性空间来实现。那当数据到了尾部如何处理呢？它将转回到0位置来处理。这个的转回是通过取模操作来执行的。

因此环列队列的是逻辑上将数组元素q[0]与q[MAXN-1]连接，形成一个存放队列的环形空间。

为了方便读写，还要用数组下标来指明队列的读写位置。head/tail.其中head指向可以读的位置，tail指向可以写的位置。

环形队列的关键是判断队列为空，还是为满。当tail追上head时，队列为满时，当head追上tail时，队列为空。但如何知道谁追上谁。还需要一些辅助的手段来判断.

如何判断环形队列为空，为满有两种判断方法。

一.是附加一个标志位tag

当head赶上tail，队列空，则令tag=0,
当tail赶上head，队列满，则令tag=1,

二.限制tail赶上head，即队尾结点与队首结点之间至少留有一个元素的空间。

队列空： head==tail
队列满： (tail+1)% MAXN ==head

二.附加标志实现算法

-------------------------------------------------------------

采用第一个环形队列有如下结构

1 typedef struct ringq{  
2    int head;   
3    int tail;    
4    int tag ;  
5    int size ;   
6    int space[RINGQ_MAX];   
7     
8 }RINGQ;

初始化状态: q->head = q->tail = q->tag = 0;

队列为空:(q->head == q->tail) && (q->tag == 0)

队列为满: ((q->head == q->tail) && (q->tag == 1))

入队操作:如队列不满，则写入

q->tail = (q->tail + 1) % q->size ;
出队操作：如果队列不空，则从head处读出。

下一个可读的位置在 q->head = (q->head + 1) % q->size

完整代码

头文件ringq.h

 1 #ifndef __RINGQ_H__  
 2 #define __RINGQ_H__  
 3   
 4 #ifdef __cplusplus  
 5 extern "C" {  
 6 #endif   
 7 
 8 #define QUEUE_MAX 20  
 9 typedef struct ringq{  
10    int head;   
11    int tail;    
12    int tag ;   
13     int size ;   
14    int space[QUEUE_MAX];   
15 }RINGQ;  
16   
17   
18 extern int ringq_init(RINGQ * p_queue);  
19 extern int ringq_free(RINGQ * p_queue);    
20 extern int ringq_push(RINGQ * p_queue,int data);  
21 extern int ringq_poll(RINGQ * p_queue,int *p_data);  
22 #define ringq_is_empty(q) ( (q->head == q->tail) && (q->tag == 0))  
23 #define ringq_is_full(q) ( (q->head == q->tail) && (q->tag == 1))  
24 #define print_ringq(q) printf("ring head %d,tail %d,tag %d
", q->head,q->tail,q->tag);  
25 #ifdef __cplusplus  
26 }  
27 #endif   
28   
29 #endif

实现代码 ringq.c

 1 #include <stdio.h>  
 2 #include "ringq.h"  
 3   
 4 int ringq_init(RINGQ * p_queue)  
 5 {  
 6    p_queue->size = QUEUE_MAX ;      
 7    p_queue->head = 0;  
 8    p_queue->tail = 0;      
 9    p_queue->tag = 0;       
10    return 0;  
11 }  
12   
13 int ringq_free(RINGQ * p_queue)  
14 {  
15     return 0;  
16 }  
17 //Write data to the queue   
18 int ringq_push(RINGQ * p_queue,int data)  
19 {  
20     print_ringq(p_queue);      
21     if(ringq_is_full(p_queue))  
22     {       
23         printf("ringq is full
");  
24         return -1;  
25     }         
26     p_queue->space[p_queue->tail] = data;      
27     p_queue->tail = (p_queue->tail + 1) % p_queue->size ;           
28     if(p_queue->tail == p_queue->head)  
29     {  
30         p_queue->tag = 1;  
31     }   
32     return p_queue->tag ;    
33 }  
34 //Get data from the queue  
35 int ringq_poll(RINGQ * p_queue,int * p_data)  
36 {  
37     print_ringq(p_queue);  
38     if(ringq_is_empty(p_queue))  
39     {        
40         printf("ringq is empty
");  
41         return -1;  
42     }      
43     *p_data = p_queue->space[p_queue->head];     
44     p_queue->head = (p_queue->head + 1) % p_queue->size ;   
45     if(p_queue->tail == p_queue->head)  
46     {  
47         p_queue->tag = 0;  
48     }      
49     return p_queue->tag ;  
50 }

测试代码

 1 void test5()  
 2 {  
 3   RINGQ rq, * p_queue;  
 4   int i,data;  
 5     
 6   p_queue = &rq;  
 7     
 8   ringq_init(p_queue);  
 9     
10   for(i=0; i < QUEUE_MAX +2 ; i++)  
11   {  
12      
13    ringq_push(p_queue,i+1);   
14   }   
15       
16   if(ringq_poll(p_queue,&data)>=0)  
17      PRINT_INT(data);  
18     
19   if(ringq_poll(p_queue,&data)>=0)  
20      PRINT_INT(data);  
21     
22   if(ringq_poll(p_queue,&data)>=0)  
23      PRINT_INT(data);  
24     
25   if(ringq_poll(p_queue,&data)>=0)  
26      PRINT_INT(data);  
27     
28   if(ringq_poll(p_queue,&data)>=0)  
29      PRINT_INT(data);  
30     
31   if(ringq_poll(p_queue,&data)>=0)  
32      PRINT_INT(data);  
33     
34   ringq_free(p_queue);  
35 }  
36   
37   
38 void test6()  
39 {  
40   RINGQ rq, * p_queue;  
41   int i,data;  
42     
43   p_queue = &rq;  
44     
45   ringq_init(p_queue);  
46     
47     
48    ringq_push(p_queue,1);   
49      
50    ringq_push(p_queue,2);   
51     
52     
53   if(ringq_poll(p_queue,&data)>=0)  
54      PRINT_INT(data);  
55     
56   if(ringq_poll(p_queue,&data)>=0)  
57      PRINT_INT(data);  
58     
59   if(ringq_poll(p_queue,&data)>=0)  
60      PRINT_INT(data);  
61     
62   if(ringq_poll(p_queue,&data)>=0)  
63      PRINT_INT(data);  
64       
65   ringq_push(p_queue,3);   
66     
67   ringq_push(p_queue,4);   
68     
69   ringq_push(p_queue,5);   
70     
71   if(ringq_poll(p_queue,&data)>=0)  
72      PRINT_INT(data);  
73     
74   if(ringq_poll(p_queue,&data)>=0)  
75      PRINT_INT(data);  
76          
77    ringq_push(p_queue,6);   
78        
79    if(ringq_poll(p_queue,&data)>=0)  
80      PRINT_INT(data);  
81        
82      if(ringq_poll(p_queue,&data)>=0)  
83      PRINT_INT(data);  
84     
85   ringq_free(p_queue);  
86 }

三.预留空间环境队列

-------------------------------------------------------------------

不采用tag,只留一个空间

初始化状态: q->head = q->tail = q->tag = 0;

队列为空:(q->head == q->tail)

队列为满: (((q->tail+1)%q->size) == q->head )

入队操作:如队列不满，则写入

q->tail = (q->tail + 1) % q->size ;
出队操作：如果队列不空，则从head处读出。

下一个可读的位置在 q->head = (q->head + 1) % q->size

头文件

ringq.h

 1 #ifndef __RINGQ_H__  
 2 #define __RINGQ_H__  
 3   
 4 #ifdef __cplusplus  
 5 extern "C" {  
 6 #endif   
 7   
 8 #define RINGQ_MAX 20  
 9   
10 typedef struct ringq{  
11    int head;   
12    int tail;    
13    int size ;   
14    int space[RINGQ_MAX];   
15 }RINGQ;  
16   
17    
18 extern int ringq_init(RINGQ * p_ringq);  
19 extern int ringq_free(RINGQ * p_ringq);   
20 extern int ringq_push(RINGQ * p_ringq,int data);    
21 extern int ringq_poll(RINGQ * p_ringq,int * p_data);  
22   
23 #define ringq_is_empty(q) (q->head == q->tail)    
24 #define ringq_is_full(q) (((q->tail+1)%q->size) == q->head )   
25 #define print_ringq2(q,d) printf("ring head %d,tail %d,data %d
", q->head,q->tail,d);  
26  
27 #ifdef __cplusplus  
28 }  
29 #endif   
30   
31 #endif

实现代码ringq.c

 1 #include <stdio.h>  
 2 #include "ringq.h"  
 3   
 4 int ringq_init(RINGQ * p_ringq)  
 5 {  
 6     p_ringq->size = RINGQ_MAX;      
 7     p_ringq->head = 0;  
 8     p_ringq->tail = 0;    
 9     return p_ringq->size;  
10 }  
11   
12 int ringq_free(RINGQ * p_ringq)  
13 {  
14     return 0;  
15 }  
16   
17   
18 int ringq_push(RINGQ * p_ringq,int data)  
19 {  
20     print_ringq(p_ringq,data);     
21     if(ringq_is_full(p_ringq))  
22     {  
23         printf("ringq is full,data %d
",data);  
24         return -1;  
25     }          
26     p_ringq->space[p_ringq->tail] = data;       
27     p_ringq->tail = (p_ringq->tail + 1) % p_ringq->size ;           
28     return p_ringq->tail ;  
29 }  
30   
31   
32 int ringq_poll(RINGQ * p_ringq,int * p_data)  
33 {  
34     print_ringq(p_ringq,-1);  
35     if(ringq_is_empty(p_ringq))  
36     {  
37         printf("ringq is empty
");  
38         return -1;  
39     }       
40     *p_data = p_ringq->space[p_ringq->head];       
41     p_ringq->head = (p_ringq->head + 1) % p_ringq->size ;      
42     return p_ringq->head;  
43 }