キューの作成と基本操作

キュー(FIFO)は一部だけ挿入し、他端は削除することができる線形表で、先入先出原則に従い、隊頭は削除し、列の最後に挿入する.
順番待ち行列
使用用配列保存 初期条件front=rear=0満行列:rear=m   容量m
空き行列:  front=rear 
構造:

typedef struct
{
	int data[MAX];
	int front,rear;
}Queue;

操作:

/     
Queue InitQueue()
{
	Queue p;
	p.front=p.rear=0;
	return p;	
}

//  
int InQueue(Queue *p,int e)
{
	p->data[++p->rear]=e;
	if(p->rear>MAX)
		return 0;
	else
	{
		printf("    
");
		return 1;	
	}			
} 

//  
int DeQueue(Queue *p,int *e)
{
	if(p->front==p->rear)
		return 0;
	else
	{
		p->front++;                 //            
		printf("    
");	
		return 0;
	}	
} 

テスト:

#include 
#include

#define MAX 10
//    ,      
//     front =rear=0
// ：rear=m    m
//   front=rear 
typedef struct
{
	int data[MAX];
	int front,rear;
}Queue;

//     
Queue InitQueue()
{
	Queue p;
	p.front=p.rear=0;
	return p;	
}

//  
int InQueue(Queue *p,int e)
{
	p->data[++p->rear]=e;
	if(p->rear>MAX)
		return 0;
	else
	{
		printf("    
");
		return 1;	
	}			
} 

//  
int DeQueue(Queue *p,int *e)
{
	if(p->front==p->rear)
		return 0;
	else
	{
		p->front++;                 //            
		printf("    
");	
		return 0;
	}	
} 

//  
void print(Queue *p)
{
	while(p->frontrear+1))
	{
		printf("%d",p->data[p->front]);
		p->front++;
	}
} 

int main()
{
	int a;
	Queue p;
	InitQueue();
	InQueue(&p,1);
	InQueue(&p,2);
	InQueue(&p,3);
	InQueue(&p,4);
	DeQueue(&p,&a);
	print(&p);
	return 0;
}

巡回キュー
frontはチームの頭の要素を指し、rearはチームの最後の要素の次の位置を指します.
front=rearの時は空き列です.
以下にいくつかの公式があります.
1.列の最大サイズMAXを設定し、列がいっぱいになる条件は.
(rear+1)%MAX==front
2.一般的な計算キューの長さの公式:
(rear-front+MAX)%MAX
ループキューの順序格納構造.

typedef  struct
{
	int data[MAX];
	int front,rear;	
}SQueue;

基本操作:

//          
int InitQueue(SQueue *q)
{
	q->front=0;
	q->rear=0;
	return 1;
} 

//       
int QueueLength(SQueue *q)
{
	return (q->rear-q->front+MAX)%MAX;
}

//  
int EnQueue(SQueue *q,int e)
{
	if((q->rear+1)%MAX==q->front)   //       
		return 0;
	q->data[q->rear]=e;
	q->rear=(q->rear+1)%MAX;		// rear       
	return 1;		
}

//  
int DeQueue(SQueue *q,int *e)
{
	if(q->front==q->rear)       //     
		return 0;
	*e=q->data[q->front];
	q->front=(q->front+1)%MAX;	   //front       
	return 1;
}

テストコード:

#include
#include

#define MAX 10

//         
 
typedef  struct
{
	int data[MAX];
	int front,rear;	
}SQueue;

//          
int InitQueue(SQueue *q)
{
	q->front=0;
	q->rear=0;
	return 1;
} 

//       
int QueueLength(SQueue *q)
{
	return (q->rear-q->front+MAX)%MAX;
}

//  
int EnQueue(SQueue *q,int e)
{
	if((q->rear+1)%MAX==q->front)   //       
		return 0;
	q->data[q->rear]=e;
	q->rear=(q->rear+1)%MAX;		// rear       
	return 1;		
}

//  
int DeQueue(SQueue *q,int *e)
{
	if(q->front==q->rear)       //     
		return 0;
	*e=q->data[q->front];
	q->front=(q->front+1)%MAX;	   //front       
	return 1;
}


//  
void print(SQueue *q)
{
	while(q->front!=q->rear)
	{
		printf("%d",q->data[q->front]);
		q->front++;
	}
}


 

int main()
{
	int a,b;
	SQueue q;
	InitQueue(&q);
	EnQueue(&q,1);
	EnQueue(&q,2);
	EnQueue(&q,3);
	EnQueue(&q,4);
	DeQueue(&q,&a);
	printf("    ：%d",QueueLength(&q));
	printf("   ："); 
	print(&q);
	return 0;
 } 
 

チェーン・キュー
後進頭に相当するチェーン時計
frontは、最初の結点ではなく、最後の結点を指す.
構造は以下の通りです

typedef struct QNode
{
	int data;
	struct QNode *next;
}QNode,QNodePtr;

typedef struct 
{
	QNodePtr front,rear;	
}LinkQueue;

基本操作:

//   
LinkQueue InitQueue(LinkQueue *p)
{
	p->front=p->rear=(QNodePtr)malloc(sizeof(QNode));
	if(!p->front)
		return 0;
	p->front->next=p->front->next=NULL;
	return p;		
} 


//  
int EnQueue(LinkQueue *q,int e)
{
	QNodePtr s=(QNodePtr)malloc(sizeof(QNode));
	s->data=e;
	s->next=NULL;
	q->rear->next=s;
	q->rear=s;    // rear        
	return 1; 
} 


//  
int DeQueue(LinkQueue *q,int *e)
{
	QNodePtr p;    //      
	if(q->front==q->rear)   //    
		return 0;
	p=q->front->next;
	*e=p->data;
	q->front->next=p->next;
	
	if(q->rear==p)    //             rear     
		q->rear=q->front;
	free(p);	 
	return 1;
} 

テストコード:

#include
#include

//          
//front            ，rear      ，       

typedef struct QNode
{
	int data;
	struct QNode *next;
}QNode,*QNodePtr;

typedef struct 
{
	QNodePtr front,rear;	
}LinkQueue;



//   
int InitQueue(LinkQueue *p)
{
	p->front=p->rear=(QNodePtr)malloc(sizeof(QNode));
	if(!p->front)
		return 0;
	p->front->next=p->rear->next=NULL;
	return 1;			
} 



//  
int EnQueue(LinkQueue *q,int e)
{
	QNodePtr s=(QNodePtr)malloc(sizeof(QNode));
	s->data=e;
	s->next=NULL;
	q->rear->next=s;
	q->rear=s;    // rear        
	return 1; 
} 


//  
int DeQueue(LinkQueue *q,int *e)
{
	QNodePtr p;    //      
	if(q->front==q->rear)   //    
		return 0;
	p=q->front->next;
	*e=p->data;
	q->front->next=p->next;
	
	if(q->rear==p)    //             rear     
		q->rear=q->front;
	free(p);	 
	return 1;
} 

void print(LinkQueue q)
{
	while(q.front!=q.rear)  
	{  
		q.front=q.front->next;   //  front                    
		printf("%d
",q.front->data);
	}
}


int main()
{
	int a;
	LinkQueue q;
	InitQueue(&q);
	EnQueue(&q,1); 
	EnQueue(&q,2); 
	EnQueue(&q,3); 
	EnQueue(&q,4); 	
	DeQueue(&q,&a);
	print(q);
	return 0;
}