tes.cpp

数据结构中相关ADT的C++实现,注解清晰,让你快速掌握

//实现循环队列
//采用少用一个元素空间约定以"队列头指针在队列尾指针的下一位置上"作为队列呈满状态的标志,队列头指针等于尾指针时队空
//除了遍历操作时间复杂度为O(N)外,其他基本操作都为O(1);
#include<iostream.h>
#define maxqsize 100
typedef struct
{
	int * base;
	int front;
	int rear;
}squeue;
void initqueue(squeue & q)
{
	//构造一个空队列
	q.base=new int[maxqsize];
	q.front=q.rear=0;
}
int queuelength(squeue q)
{
	return (q.rear-q.front+maxqsize)%maxqsize;
}
void enqueue(squeue & q,int e)
{
	//插入元素e为q的队尾元素
	if(((q.rear+1)%maxqsize)==q.front)
		return ;
	q.base[q.rear]=e;
	q.rear=(q.rear+1)%maxqsize;

}
void dequeue(squeue & q,int & e)
{
	//若队列不空,则删除q的队列元素,用e返回其值;
	//否则终止;
	if(q.front==q.rear)return ;
	e=q.base[q.front];
	q.front=(q.front+1)%maxqsize;

}
void queuetrave(squeue q)
{
//遍历队列
	int k=0,i=q.front;
while(i!=q.rear)
{
	if(k%10==0)cout<<endl;
		cout<<q.base[i]<<" ";
		k++;
		i=(i+1)%maxqsize;

	}
}
void main()
{
	//构造一个空队列,插入50个元素
	//计算队列长度
	//删除20个元素
	//遍历队列
	squeue q;
	int e;
	initqueue(q);
	for(int i=0;i<50;i++)
	{
		enqueue(q,i);
	}
	cout<<"队列长度"<<queuelength(q)<<endl;
	for(i=0;i<20;i++)
	{
dequeue(q,e);
	}
	cout<<"遍历队列"<<endl;
	queuetrave(q);
}