当先锋百科网

首页 1 2 3 4 5 6 7

循环队列(一)

队列
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
循环队列
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。
在这里插入图片描述
消除假溢出就是当队尾指针rear和队头指针front到达存储空间最大值Maxsize时,让队尾指针自动转化为存储空间的最小值0,但是有新问题:在循环队列中,空队特征是front = rear, 队满时也会有front = rear; 判断条件将出现二义性
解决方案有三种:

  1. 使用一个计数器记录队列中元素个数(即队列长度)
  2. 人为浪费一个单元,令队满特征为 front = (rear +1)%N(N为队列最大存储空间)
  3. 加设标志位,让删除动作使其为1,插入动作使其为0, 则可识别当前front == rear;
    方案一:
    queue.cpp
    主函数调用
#include<stdio.h>
#include<stdlib.h>
#include"malloc.h"
#include"queue.h"
#include"queueimpl.cpp"
int  main()
{
	int a[10];
	
	queue* q = (queue *)malloc(sizeof(queue));;//定义一个节点 
	CreateQueue(q, 9);//初始化空队列
	
	printf("元素入队......\n"); 
	for(int i=1;i<10;i++)
		Enqueue(q,i);
	printf("队中的元素是:\n");	
	TraverseQueue(q);
	
	printf("元素出队......\n");
	printf("出队的元素是:\n");
	for(int j=0;j<5;j++){
		Dequeue(q,&a[j]);
		printf("%d ",a[j]);
	}
	printf("\n队中剩余的元素是:\n");	
	TraverseQueue(q); 
	
	return 0;
}


queue.h
头文件定义

#ifndef __QUEUE_H_
#define __QUEUE_H_
typedef struct queue 
{
	int *pBase;
	int front;    //指向队列第一个元素
	int rear;    //指向队列最后一个元素的下一个元素
	int maxsize; //循环队列的最大存储空间
	int count;//记录循环队列的已占用的存储空间 
}QUEUE,*PQUEUE;
 
void CreateQueue(PQUEUE Q,int maxsize);
void TraverseQueue(PQUEUE Q);
bool FullQueue(PQUEUE Q);
bool EmptyQueue(PQUEUE Q);
bool Enqueue(PQUEUE Q, int val);
bool Dequeue(PQUEUE Q, int *val);
#endif

queueimpl.cpp
实现queue.h文件中的函数

#include "queue.h"
/***********************************************
Function: Create a empty queue;
************************************************/
void CreateQueue(PQUEUE Q,int maxsize)
{
	Q->pBase=(int *)malloc(sizeof(int)*maxsize);
	if(NULL==Q->pBase)
	{
		printf("Memory allocation failure");
		exit(-1);        //退出程序
	}
	Q->front=0;         //初始化参数
	Q->rear=0;
	Q->count=0; 
	Q->maxsize=maxsize;
}
/***********************************************
Function: Print the queue element;
************************************************/
void TraverseQueue(PQUEUE Q)
{
	int i=Q->front;
//	printf("队中的元素是:\n");
	if(!FullQueue(Q)){
		while(i%Q->maxsize!=Q->rear)
	{
		printf("%d ",Q->pBase[i]);
		i++;
	}
	printf("\n");	
	}
	else
	{
		for(int j=0;j<Q->maxsize;j++)
	{
		printf("%d ",Q->pBase[i]);
		i++;
	}
	printf("\n");	
	}
}
bool FullQueue(PQUEUE Q)
{
	if(Q->front==(Q->rear)%Q->maxsize&&Q->count==Q->maxsize)
		return true;
	else
		return false;
}
bool EmptyQueue(PQUEUE Q)
{
	if(Q->count==0)
		return true;
	else
		return false;
}
bool Enqueue(PQUEUE Q, int val)
{
	if(FullQueue(Q))
		return false;
	else
	{
		Q->pBase[Q->rear]=val;
		Q->rear=(Q->rear+1)%Q->maxsize;
		Q->count++;
		return true;
	}
}
 
bool Dequeue(PQUEUE Q, int *val)
{
	if(EmptyQueue(Q))
	{
		return false;
	}
	else
	{
		*val=Q->pBase[Q->front];
		Q->front=(Q->front+1)%Q->maxsize;
		Q->count--;
		return true;
	}
}


个人见解,如有不对,还去见谅,欢迎评论修改!