环形队列实现原理 链式实现.docx

环形队列实现原理 /链式实现环形队列是在实际编程极为有用的数据结构,它有如下特点。 它是一个首尾相连的FIFO的数据结构，采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。 因为有简单高效的原因，甚至在硬件都实现了环形队列. 环形队列广泛用于网络数据收发，和不同程序间数据交换（比如内核与应用程序大量交换数据,从硬件接收大量数据）均使用了环形队列.一.环形队列实现原理- 内存上没有环形的结构，因此环形队列实上是数组的线性空间来实现。那当数据到了尾部如何处理呢？它将转回到0位置来处理。这个的转回是通过取模操作来执行的。 因此环列队列的是逻辑上将数组元素q0与qMAXN-1连接，形成一个存放队列的环形空间。 为了方便读写，还要用数组下标来指明队列的读写位置。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二.附加标志实现算法采用第一个环形队列有如下结构typedef struct ringq int head; /* 头部，出队列方向*/ int tail; /* 尾部，入队列方向*/ int tag ; int size ; /* 队列总尺寸 */ int spaceRINGQ_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_#ifdef _cplusplusextern C #endif#define QUEUE_MAX 20 typedef struct ringq int head; /* 头部，出队列方向*/ int tail; /* 尾部，入队列方向*/ int tag ; /* 为空还是为满的标志位*/ int size ; /* 队列总尺寸 */ int spaceQUEUE_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(ring head %d,tail %d,tag %dn, q-head,q-tail,q-tag);#ifdef _cplusplus#endif#endif /* _RINGQ_H_ */实现代码 ringq.c#include #include ringq.hint 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 fulln); return -1; p_queue-spacep_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 emptyn); return -1; *p_data = p_queue-spacep_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 = 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_#ifdef _cplusplusextern C #endif #define RINGQ_MAX 20typedef struct ringq int head; /* 头部，出队列方向*/ int tail; /* 尾部，入队列方向*/ int size ; /* 队列总尺寸 */ int spaceRINGQ_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(ring head %d,tail %d,data %dn, q-head,q-tail,d);#ifdef _cplusplus#endif #endif /* _QUEUE_H_ */实现代码ringq.c#include #include ringq.hint 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 %dn,data); return -1; p_ringq-spacep_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 emptyn); return -1; *p_data = p_ringq-spacep_ringq-head; p_ringq-head = (p_ringq-head + 1) % p_ringq-size ; return p_ringq-head;作者：Andrew H环形队列的链式实现from:/herbert/archive/2011/01/17/1937787.html程序是用codeblock写的，中间碰到了一个又一个的问题，都最终解决了。这个结构可以作为所有结构体的实现的一个模式。写写这些程序可以不断让自己更加深入认识指针，更加熟悉指针的各种使用。经常锻炼C基础，心里写程序更有底.#include #include #include typedef int Queue_Type;/ 定义队列节点结构typedef struct CQUEUE_NODE Queue_Type value; struct CQUEUE_NODE *next;QNode, *PNode;/ 定义队列结构typedef struct CQUEUE unsigned int size; PNode front, retail;LQueue;/创建环形队列void Create_Queue(LQueue *L, int n) PNode front = (PNode)malloc(sizeof(QNode); PNode retail = (PNode)malloc(sizeof(QNode); if(front = NULL | retail = NULL) exit(1); scanf(%d, &front-value); front-next = NULL; / 只有一个节点的时候，头尾指向同一个点 retail = front; / 多个点情况 int i; for(i = 1; i value); retail-next = p; retail = p; / 结束后，尾节点指向头节点 retail-next = front; L-front = (PNode)malloc(sizeof(QNode); L-retail = (PNode)malloc(sizeof(QNode); if(L-front = NULL | L-retail = NULL) exit(1); L-front = front; L-retail = retail; L-size = n;/ 销毁队列void Destory_Queue(LQueue *L) / 如果队列为空 if(L-front = NULL) exit(1); / 这里注意必须重新申请一个节点 / 直接使用L-retail-next会有类型不能识别的错误 PNode p = (PNode)malloc(sizeof(QNode); if(p = NULL) exit(1); p = L-front; int size = L-size; / 队列是多个节点情况 while(size != 0) L-front = p-next; free(p); p = L-front; size-; / 这里一定要记得处理 / 将front retail指向NULL 在上面的处理过程中，只是free并没有指向NULL / 如果不指向NULL, front,retail将是野指针 / 还要记得将L-size重新赋值，上面size只是读取size，并不改变size的值 L-front = NULL; L-retail = NULL; L-size = size;/ 入列操作 在尾节点插入void Enqueue(LQueue *L, Queue_Type value) PNode p = (PNode)malloc(sizeof(QNode); if(p = NULL) exit(1); p-value = value; int size = L-size; /如果队列是个空队列 if(size = 0) L-front = (PNode)malloc(sizeof(QNode); L-retail = (PNode)malloc(sizeof(QNode); L-front = p; L-retail = p; p-next = NULL; size +; / 如果队列不是空队列 / 头节点倒是没有必要重新开辟空间 PNode p1 = (PNode)malloc(sizeof(QNode); if(p1 = NULL) exit(1); p1 = L-retail; p1-next = p; p-next = L-front; L-retail = p; /这里没发现啊，害我找了很久 size+; L-size = size;/ 出列操作Queue_Type Dequeue(LQueue *L) int size = L-size; Queue_Type n; /如果队列为空 if(size = 0) printf(The queue is empty.n); exit(1); PNode p = (PNode)malloc(sizeof(QNode); if(p = NULL) exit(1); p = L-front; /如果队列只有一个节点 if(size = 1) n = p-value; free(p); L-front = L-retail = NULL; p = NULL; size-; L-size = size; return n; if(size = 2) n = p-value; L-front = L-retail; free(p); p = NULL; size-; L-size = size; return n; / 头节点倒是没有必要重新开辟空间 PNode p1 = (PNode)malloc(sizeof(QNode); if(p1 = NULL) exit(1); p1 = L-retail; n = p-value; L-front = p-next; p1-next = L-front; free(p); p = NULL; size-; L-size = size; return n;/ 判断队列是否为空bool Is_Empty(LQueue L) if(L.size = 0) return false; else return true;/ 打印队列void Print_Queue(LQueue L) / 如果队列为空 if(L.size = 0) printf(The size of the queue is: %dn, L.size); exit(1); printf(The size of the queue is: %dn, L.size); printf(The following are the elements of the queue:n); PNode p = (PNode)malloc(sizeof(QNode); if(p = NULL) exit(1); p = L.front; while(p != L.retail) printf(%dn, p-value); p = p-next; if(p = L.retail) printf(%dn, p-value); int main() LQueue L; int n; printf(Input the number of the nodes of the queue:n); scanf(%d, &n); printf(-n); Create_Queue(&L, n); printf(-n); Print_Queue(L); printf(-n); printf(Enqueue a node:n); int n1, n2,n3; scanf(%d, &n1); Enqueue(&L, n1); printf(-n);