고리 형 대기 열 실현 원리 / 체인 식 실현
링 대기 열 은 실제 프로 그래 밍 에서 매우 유용 한 데이터 구조 로 다음 과 같은 특징 을 가지 고 있다.
이것 은 처음부터 끝까지 연 결 된 FIFO 의 데이터 구조 로 배열 의 선형 공간 을 사용 하고 데이터 조직 이 간단 하 다.대기 열 이 비어 있 는 지 빨리 알 수 있 습 니 다.빠 른 속도 로 데 이 터 를 액세스 할 수 있 습 니 다.
간단 하고 효율 적 인 원인 이 있 기 때문에 심지어 하드웨어 에서 도 링 대기 열 을 실현 했다.
링 대기 열 은 네트워크 데이터 송 수신 에 광범 위 하 게 사용 되 고 서로 다른 프로그램 간 데이터 교환 (예 를 들 어 커 널 과 응용 프로그램 이 데 이 터 를 대량으로 교환 하고 하드웨어 에서 대량의 데 이 터 를 수신) 은 모두 링 대기 열 을 사용 합 니 다.
1. 환형 대열 실현 원리
------------------------------------------------------------
메모리 에 링 구조 가 없 기 때문에 링 대기 열 은 사실상 배열 의 선형 공간 으로 이 루어 진다.그럼 데이터 가 끝 에 도착 하면 어떻게 처리 합 니까?그것 은 0 위치 로 돌아 가 처리 할 것 이다.이것 의 회 귀 는 모델 링 작업 을 통 해 실 행 된 것 이다.
따라서 순환 대기 열 은 논리 적 으로 배열 요소 q [0] 와 q [MAXN - 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
2. 부가 표지 실현 알고리즘 은 첫 번 째 링 대기 열 을 사용 하여 다음 과 같은 구 조 를 가진다.
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__ #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("ring head %d,tail %d,tag %d
", q->head,q->tail,q->tag); #ifdef __cplusplus } #endif #endif /* __RINGQ_H__ */
实现代码 ringq.c
#include
"); 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
"); 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__ #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("ring head %d,tail %d,data %d
", q->head,q->tail,d); #ifdef __cplusplus } #endif #endif /* __QUEUE_H__ */
实现代码ringq.c
#include
",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
"); return -1; } *p_data = p_ringq->space[p_ringq->head]; p_ringq->head = (p_ringq->head + 1) % p_ringq->size ; return p_ringq->head; }
作者：
Andrew Huang [email protected]
环形队列的链式实现
from:http://www.cnblogs.com/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 < n; i++)
{
PNode p = (PNode)malloc(sizeof(QNode));
if(p == NULL)
exit(1);
scanf("%d", &p->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.
");
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: %d
", L.size);
exit(1);
}
printf("The size of the queue is: %d
", L.size);
printf("The following are the elements of the queue:
");
PNode p = (PNode)malloc(sizeof(QNode));
if(p == NULL)
exit(1);
p = L.front;
while(p != L.retail)
{
printf("%d
", p->value);
p = p->next;
}
if(p == L.retail)
{
printf("%d
", p->value);
}
}
int main()
{
LQueue L;
int n;
printf("Input the number of the nodes of the queue:
");
scanf("%d", &n);
printf("-------------------------------------------
");
Create_Queue(&L, n);
printf("-------------------------------------------
");
Print_Queue(L);
printf("-------------------------------------------
");
printf("Enqueue a node:
");
int n1, n2,n3;
scanf("%d", &n1);
Enqueue(&L, n1);
printf("-------------------------------------------
");
Print_Queue(L);
printf("Dequeue one node -------------------------
");
n2 = Dequeue(&L);
printf("Node1 is %d
",n2);
Print_Queue(L);
printf("Dequeue another node -------------------------
");
n3 =Dequeue(&L);
printf("Node2 is %d
",n3);
Print_Queue(L);
printf("-------------------------------------------
");
printf("Destory the queue---------------------------
");
Destory_Queue(&L);
Print_Queue(L);
return 0;
}
， 。
몇 가지 문 제 를 특별히 주의해 야 한다.
1. 구 조 는 매개 변수 로 전달 된다.이 전달 방식 도 다른 것 과 같 습 니 다. 들 어 오 는 매개 변수의 값 을 바 꿔 야 할 때 주소 로 전달 하고 포인터 파 라 메 터 를 사용 합 니 다.매개 변수의 전달 은 일반적인 int 와 유사 하 므 로 구조 체 지침 을 사용 하면 됩 니 다.
둘째, 구조 체 매개 변수 값 전달 과 주소 전달 의 호출 방식 이 다르다.구조 체 매개 변 수 는 일반 값 으로 매개 변 수 를 전달 할 경우 구조 체, 구성원 을 사용 하여 접근 합 니 다.주소 로 전달 된다 면 포인터 파라미터 가 들 어 오 는 구조 체 - > 구성원 이 방문 하 는 것 입 니 다.이것 이 바로 구조 체 와 구조 체 포인터 가 데이터 구성원 에 게 접근 하 는 차이 이다.
3. 대기 열 과 같이 머리 꼬리 대기 열 점 을 포함 하 는 구조 체 는 초기 화 할 때 모든 포인터 구조 에 공간 을 신청 해 야 합 니 다. 즉, 안에 있 는 것 입 니 다.
L->front = (PNode)malloc(sizeof(QNode)); L->retail = (PNode)malloc(sizeof(QNode));
4. 구조 체 구성원 포인터 가 가리 키 는 데 이 터 를 가 져 올 때 사용 하지 마 십시오. 구조 체 포인터 - > 포인터 구성원 - > 포인터 구성원 이 가리 키 는 데이터.이렇게 여러 개의 '- >' 연결 로 인해 컴 파일 이 '구조 체 지침 - > 지침 구성원' 이라는 지침 유형 을 식별 하지 못 하고 잘못 보고 할 수 있 습 니 다.상응하는 처리 방법 은 지침 을 신청 하여 그것 을 가리 키 면 된다.그리고 이 지침 을 조작 하 세 요.
5. 특정한 임계 점 상황 에 대한 처 리 는 신중 해 야 한다. 예 를 들 어 대기 열 데이터 점 이 0, 1, 2 라 는 몇 가지 상황 은 링 대기 열 에 대해 다 르 기 때문에 추가 적 인 주의 가 필요 하 다.
구체 적 인 알고리즘 은 위의 프로그램 안에 모두 있다.간단 한 테스트 를 거 쳤 으 니 문제 없 을 겁 니 다.
가 는 길에 CODEBLOCK 의 debug 를 말씀 드 리 겠 습 니 다. 지금까지 저 는 어떻게 사용 하 는 지 잘 모 르 겠 습 니 다. Watch 변 수 를 몇 번 넣 어도 반응 이 좋 지 않 고 실 수 를 했 습 니 다. 한 명 씩 만 분석 할 수 있 습 니 다.주: 이 문 제 는 나중에 관련 포럼 을 찾 아 보 았 습 니 다.
원래 codeblock 에 서 는 항목 경로 에 빈 칸 과 중국어 문자 가 있 는 것 을 허용 하지 않 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
