Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1300110
  • 博文数量: 311
  • 博客积分: 7778
  • 博客等级: 少将
  • 技术积分: 4185
  • 用 户 组: 普通用户
  • 注册时间: 2009-11-09 19:59
个人简介

蓝点工坊(http://www.bluedrum.cn) 创始人,App和嵌入式产品开发。同时也做相应培训和外包工作。 详细介绍 http://pan.baidu.com/s/1y2g88

文章存档

2012年(3)

2011年(115)

2010年(170)

2009年(23)

分类: C/C++

2010-10-09 17:17:49

Andrew Haung bluedrum@163.com 转载请注明作者和联络方式
 
环形队列是在实际编程极为有用的数据结构,它有如下特点。
   它是一个首尾相连的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
 
 
 
二.附加标志实现算法
-------------------------------------------------------------
 
  采用第一个环形队列有如下结构

typedef struct ringq{
   int head; /* 头部,出队列方向*/
   int tail; /* 尾部,入队列方向*/
   int tag ;
   int size ; /* 队列总尺寸 */
   int space[RINGQ_MAX]; /* 队列空间 */
  
}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
  

#ifndef __RINGQ_H__
#define __RINGQ_H__

/*
  Author: Andrew Huang
  document: http://blog.chinaunix.net/u3/105675/showart.php?id=2348044
*/


#ifdef __cplusplus
extern "C" {
#endif

#define QUEUE_MAX 20

typedef struct ringq{
   int head; /* 头部,出队列方向*/
   int tail; /* 尾部,入队列方向*/
   int tag ; /* 为空还是为满的标志位*/
    int size ; /* 队列总尺寸 */
   int space[QUEUE_MAX]; /* 队列空间 */
}RINGQ;

/*
  第一种设计方法:
     当head == tail 时,tag = 0 为空,等于 = 1 为满。
*/


extern int ringq_init(RINGQ * p_queue);

extern int ringq_free(RINGQ * p_queue);


/* 加入数据到队列 */
extern int ringq_push(RINGQ * p_queue,int data);

/* 从队列取数据 */
extern int ringq_poll(RINGQ * p_queue,int *p_data);


#define ringq_is_empty(q) ( (q->head == q->tail) && (q->tag == 0))

#define ringq_is_full(q) ( (q->head == q->tail) && (q->tag == 1))

#define print_ringq(q) printf("%s:ring head %d,tail %d,tag %d\n",__FUNCTION__,q->head,q->tail,q->tag);


#ifdef __cplusplus
}
#endif

#endif /* __RINGQ_H__ */

 
实现代码 ringq.c
 

#include <stdio.h>
#include "ringq.h"

/*
 
  ring queue 实现代码g
  Author: Andrew Huang
  document: http://blog.chinaunix.net/u3/105675/showart.php?id=2348044
*/



int ringq_init(RINGQ * p_queue)
{
   p_queue->size = QUEUE_MAX ;
   
   p_queue->head = 0;
   p_queue->tail = 0;
   
   p_queue->tag = 0;
   
   return 0;
}

int ringq_free(RINGQ * p_queue)
{
  return 0;
}


int ringq_push(RINGQ * p_queue,int data)
{
  print_ringq(p_queue);
  
  if(ringq_is_full(p_queue))
   {
     
     printf("ringq is full\n");
     return -1;
   }
   
   
   p_queue->space[p_queue->tail] = data;
   
   p_queue->tail = (p_queue->tail + 1) % p_queue->size ;
   
   /* 这个时候一定队列满了*/
   if(p_queue->tail == p_queue->head)
    {
       p_queue->tag = 1;
    }
    
    
    return p_queue->tag ;
  
}


int ringq_poll(RINGQ * p_queue,int * p_data)
{
   print_ringq(p_queue);
  if(ringq_is_empty(p_queue))
   {
      
      printf("ringq is empty\n");
     return -1;
   }
   
   *p_data = p_queue->space[p_queue->head];
   
   p_queue->head = (p_queue->head + 1) % p_queue->size ;
   
    /* 这个时候一定队列空了*/
   if(p_queue->tail == p_queue->head)
    {
       p_queue->tag = 0;
    }
    
    return p_queue->tag ;
}


测试代码

/* 测试第一种环形队列*/
void test5()
{
  RINGQ rq, * p_queue;
  int i,data;
  
  p_queue = &rq;
  
  ringq_init(p_queue);
  
  for(i=0; i < QUEUE_MAX +2 ; i++)
  {
   
   ringq_push(p_queue,i+1);
  }
  
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  ringq_free(p_queue);
}


/* 测试第一种环形队列,更加复杂的情况*/
void test6()
{
  RINGQ rq, * p_queue;
  int i,data;
  
  p_queue = &rq;
  
  ringq_init(p_queue);
  
  
   ringq_push(p_queue,1);
   
   ringq_push(p_queue,2);
  
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  
  ringq_push(p_queue,3);
  
  ringq_push(p_queue,4);
  
  ringq_push(p_queue,5);
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
     
     
   ringq_push(p_queue,6);
     
   if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
     
     if(ringq_poll(p_queue,&data)>=0)
     PRINT_INT(data);
  
  ringq_free(p_queue);
}

 
三.预留空间环境队列
 
 -------------------------------------------------------------------
 
不采用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
   

#ifndef __RINGQ_H__
#define __RINGQ_H__


/*
  Author: Andrew Huang
  document: http://blog.chinaunix.net/u3/105675/showart.php?id=2348044
*/


#ifdef __cplusplus
extern "C" {
#endif

#define RINGQ_MAX 20

typedef struct ringq{
   int head; /* 头部,出队列方向*/
   int tail; /* 尾部,入队列方向*/
   int size ; /* 队列总尺寸 */
   int space[RINGQ_MAX]; /* 队列空间 */
}RINGQ;


/*
 取消tag .限制读与写之间至少要留一个空间
  队列空 head == tail .
  队列满是 (tail+1)%MAX == head
  
  初始化是head = tail = 0;
  
  
*/



extern int ringq_init(RINGQ * p_ringq);

extern int ringq_free(RINGQ * p_ringq);


extern int ringq_push(RINGQ * p_ringq,int data);

extern int ringq_poll(RINGQ * p_ringq,int * p_data);


#define ringq_is_empty(q) (q->head == q->tail)


#define ringq_is_full(q) (((q->tail+1)%q->size) == q->head )


#define print_ringq2(q,d) printf("%s:ring head %d,tail %d,data %d\n",__FUNCTION__,q->head,q->tail,d);


#ifdef __cplusplus
}
#endif


#endif /* __QUEUE_H__ */

 
 

实现代码ringq.c

#include <stdio.h>

#include "ringq.h"


/*
  Author: Andrew Huang
  document: http://blog.chinaunix.net/u3/105675/showart.php?id=2348044
*/



int ringq_init(RINGQ * p_ringq)
{
  p_ringq->size = RINGQ_MAX;
  
  p_ringq->head = 0;
  p_ringq->tail = 0;
  
  return p_ringq->size;
}


int ringq_free(RINGQ * p_ringq)
{
  return 0;
}

/* 往队列加入数据 */
int ringq_push(RINGQ * p_ringq,int data)
{
   print_ringq(p_ringq,data);
   
   if(ringq_is_full(p_ringq))
     {
         printf("ringq is full,data %d\n",data);
           return -1;
     }
     
     
   p_ringq->space[p_ringq->tail] = data;
   
   p_ringq->tail = (p_ringq->tail + 1) % p_ringq->size ;
   
  
    
    return p_ringq->tail ;
}


int ringq_poll(RINGQ * p_ringq,int * p_data)
{
   print_ringq(p_ringq,-1);
  if(ringq_is_empty(p_ringq))
   {
      
      printf("ringq is empty\n");
     return -1;
   }
   
   *p_data = p_ringq->space[p_ringq->head];
   
   p_ringq->head = (p_ringq->head + 1) % p_ringq->size ;
   
   return p_ringq->head;
}


四.附加问题
--------------------------------------------------
 1.在多线程的操作中,环形队列需要加锁吗?
    需要,因为head,tail,tag都是读写可以一起访问
 
 2.队列空间可以编程中指定吗?
    可以用malloc来动态分配空间,其中的size就是为此准备
 
 
 
  3.队列中的data换成任意类型。如何修改代码?
 
 
  
 
  
 





 

阅读(2281) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

KiraVerSacE2013-01-05 21:37:46

发现了这篇博文中的一个错误
http://blog.chinaunix.net/uid-20587912-id-405149.html
三.预留空间环境队列  这个当中的C代码有个地方可能有点问题
int ringq_push(RINGQ * p_ringq,int data)
{
   print_ringq(p_ringq,data);
   
   if(ringq_is_full(p_ringq))
     {
         printf("ringq is full,data %d\n"