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;
出队操作：如果队列不空，则从head处读出。
下一个可读的位置在q->head = (q->head + 1) % q->size
头文件
ringq.h
#ifndef __RINGQ_H__
#define __RINGQ_H__
#ifdef __cplusplus
extern "C" {
#endif
#define RINGQ_MAX 20
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_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 ;
#include "ringq.h"
int ringq_init(RINGQ * p_ringq)
{
p_ringq->size = RINGQ_MAX;
p_ringq->head = 0;
p_ringq->tail = 0;
下一个可读的位置在q->head = (q->head + 1) % q->size
完整代码
头文件ringq.h
#ifndef __RINGQ_H__
#define __RINGQ_H__
#ifdef __cplusplus
extern "C" {
#endif
#define QUEUE_MAX 20
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 )
{
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;
typedef struct ringq{
int head; /*头部，出队列方向*/
int tail; /*尾部，入队列方向*/
int size ; /*队列总尺寸*/
int space[RINGQ_MAX]; /*队列空间*/
}RINGQ;
/*
取消tag .限制读与写之间至少要留一个空间
队列空head == tail .
当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);
PRINT_INT(data);
if(ringq_poll(p_queue, &data) >= 0)
PRINT_INT(data);
ringq_free(p_queue);
}
三.预留空间环境队列
-------------------------------------------------------------------
/*这个时候一定队列空了*/
if(p_queue->tail == p_queue->head)
{
p_queue->tag = 0;
}
return p_queue->tag ;
}
测试代码
/*测试第一种环形队列*/
void test5()
{
RINGQ rq, * p_queue;
int i, data;
队列为空:(q->head == q->tail) && (q->tag == 0)
队列为满: ((q->head == q->tail) && (q->tag == 1))
入队操作:如队列不满，则写入
q->tail = (q->tail + 1) % q->size ;
出队操作：如果队列不空，则从head处读出。
typedef struct ringq
{
int head; /*头部，出队列方向*/
int tail; /*尾部，入队列方向*/
int tag ;
int sizபைடு நூலகம் ; /*队列总尺寸*/
int space[RINGQ_MAX]; /*队列空间*/
}RINGQ;
初始化状态: q->head = q->tail = q->tag = 0;
环形队列实现原理/链式实现
环形队列是在实际编程极为有用的数据结构,它有如下特点。
它是一个首尾相连的FIFO的数据结构，采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。
因为有简单高效的原因，甚至在硬件都实现了环形队列.
环形队列广泛用于网络数据收发，和不同程序间数据交换（比如内核与应用程序大量交换数据,从硬件接收大量数据）均使用了环形队列.
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)
#include "ringq.h"
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)
/*从队列取数据*/
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))
队列满是(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);
为了方便读写，还要用数组下标来指明队列的读写位置。head/tail.其中head指向可以读的位置，tail指向可以写的位置。
环形队列的关键是判断队列为空，还是为满。当tail追上head时，队列为满时，当head追上tail时，队列为空。但如何知道谁追上谁。还需要一些辅助的手段来判断.
如何判断环形队列为空，为满有两种判断方法。
1.是附加一个标志位tag
当head赶上tail，队列空，则令tag=0,
当tail赶上head，队列满，则令tag=1,
2.限制tail赶上head，即队尾结点与队首结点之间至少留有一个元素的空间。
队列空：head==tail
队列满：(tail+1)% MAXN ==head
二.附加标志实现算法