queue.h

数据结构基本算法实现 用C++实现理发馆防真功能

typedef struct{
	int ArrivalTime;
	int Duration;
}QElemType;
//typedef int status;
typedef struct QNode{  //结点类型
 QElemType data;
 struct QNode *next;
}QNode,*QueuePtr;

typedef struct{        //链队列类型
	QueuePtr front;    //队头指针
	QueuePtr rear;     //队尾指针
}LinkQueue;

/*void ERRORMESSAGE(char *s)    //出错信息处理函数
{
 cout<<s<<endl;
 exit(1);
}*/

status InitQueue(LinkQueue &Q)
{//构造一个空队列Q
	Q.front=Q.rear=new QNode;
	if(!Q.front) ERRORMESSAGE("OVERFLOW");  //存储分配失败
	Q.front->next=NULL;
	return OK;
}

status DestroyQueue(LinkQueue &Q)
{//销毁队列Q
	while(Q.front){
		Q.rear=Q.front->next;
		delete(Q.front);
		Q.front=Q.rear;
	}
	return OK;
}

status ClearQueue(LinkQueue &Q)
{//将Q清为空队列
	if(!Q.front) return ERROR;
	while(Q.front->next){
		Q.rear=Q.front->next;
		Q.front->next=Q.rear->next;
		delete(Q.rear);
	}
	Q.rear=Q.front;
	return OK;
}

status QueueEmpty(LinkQueue Q)
{//若队列Q为空队列，则返回TRUE，否则返回FALSE
	if(!Q.front->next) return TRUE;
	return FALSE;
}

int QueueLength(LinkQueue Q)
{//返回Q的元素个数
 int k=0;
 QueuePtr p;
	p=Q.front;
	while(p->next){
		p=p->next;
		++k;
	}
	return k;
}
	
status GetHead(LinkQueue Q,QElemType &e)
{//用e返回Q的对头元素
	if(!Q.front->next) return ERROR;
	e=Q.front->next->data;
	return OK;
}

status EnQueue(LinkQueue &Q,QElemType e)
{//插入元素e为Q的新的队尾元素
    QueuePtr p;
	p=new QNode;
	if(!p) ERRORMESSAGE("OVERFLOW");
	p->data=e; p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}

status DeQueue(LinkQueue &Q,QElemType &e)
{//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR
   QueuePtr p;	
    if(Q.front==Q.rear) return ERROR;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p) Q.rear=Q.front;
	delete(p);
	return OK;
}

/*status QueueTraverse(LinkQueue Q,status (*visit)(QueuePtr))
{//输出队列
    QueuePtr p;
    if(Q.front->next==NULL) return ERROR;
	p=Q.front->next;
	while(p){
		(*visit)(p);
		p=p->next;
	}
	return OK;
}*/
status QueueTraverse(LinkQueue Q,status (*visit1)(QueuePtr))
{//输出队列
    QueuePtr p;
    if(Q.front->next==NULL) return ERROR;
	p=Q.front->next;
	while(p){
		(*visit1)(p);
		p=p->next;
	}
	return OK;
}

status visit1(QueuePtr p)          
{                             //输出结点p的元素  
	cout<<p->data.ArrivalTime<<",";
	cout<<p->data.Duration<<",";
	return OK;
}