zhizheng.cpp

队列

#define NULL 0
#include <iostream.h>
#include <windows.h>
#include <stdio.h>
template<class Type>class Queue;
template<class Type>class QueueNode{
	friend class Queue<Type>;
	private:
		Type data;
		QueueNode<Type>*link;
	public:
		QueueNode(Type d=0,QueueNode*l=NULL):data(d),link(l){}
};
template<class Type>class Queue{
 
 private:
		QueueNode<Type>*p;
	public:
		Queue():p(NULL){}
		~Queue();
		void EnQueue(const Type&item);
		Type DeQueue();
		Type GetFront();
		void MakeEmpty();
		int IsEmpty()const{return p==NULL;}
		
		void Create(Type a[],int n)
			{
   QueueNode<Type> *q;

	p=q=new QueueNode<Type>;

	for(int i=0;i<n;i++)
	{
		q->link = new QueueNode<Type>(a[i]);
	    q=q->link;
	}

	q->link=NULL;
}

		QueueNode<Type> *Locate(int i)
		{
			if(i<-1) return NULL;
			if(i==-1) return p;
			QueueNode<Type> *q=p->link;
			int j=0;
			while(q!=NULL&&j<i)
			{
				q=q->link;
				j++;
			}
			return q;
		}
		Type Display(int i)
		{
		QueueNode<Type> *q=Locate(i);
			if(q== NULL||q==p)
				return NULL;
			else return q->data;
		}
		
	
};
template<class Type>Queue<Type>::~Queue(){
	QueueNode<Type>*s;
	while(p!=NULL){s=p;p=p->link;
	delete s;}
}
template<class Type>void Queue<Type>::EnQueue(const Type&item)
{
	 if ( p == NULL )
	{
	     p = new QueueNode<Type>(item,NULL);
 
		 p->link = p;
	}
    else
	{
		QueueNode<Type> *s = new QueueNode<Type>(item,NULL);
		
		s->link = p->link;

		p= p->link =s; 
	}
}
template<class Type>Type Queue<Type>::DeQueue(){
	if(p==NULL)
	{
		cout<<"队列空，不能删除！"<<endl;return 0;}
	QueueNode<Type>*s=p->link;
	if(s==NULL){s=p;p=NULL;}
	else p->link=s->link;
	Type retvalue=s->data;
	delete s;
	return retvalue;
}
void main()
{
    cout<<"1、请输入要构造队列的长度(输入一个整数)："<<endl;

	int count;
	
	cin>>count;

	cout<<endl;

	cout<<"2、请输入用于构造队列的数组s的元素(输入整数)："<<endl;
    
	int s[30];
	
	for(int i=0;i<count;i++)
	{
     cin>>s[i];
	}

	cout<<endl<<endl;

	Queue <int> Queue1;
    
    Queue1.Create(s,count);     //用数组建立链表
	
	cout<<"根据您的输入，用s建立的队列为：";
    
	for(int k=0;k<count;k++)
	{
	  i=Queue1.Display(k);
	  cout<<i<<' ';
}
	cout<<endl;
     int m;
	 cout<<"请输入你想插入的数:";

	 cin>>m;
	Queue1.EnQueue(m);
   	for(k=0;k<count;k++)
	{
		i=Queue1.Display(k);

	    cout<<i<<' ';
	}
	cout<<m<<endl;
  cout<<endl;
    cout<<"经过出队算法后得到的队列为:";
	Queue1.DeQueue();
   		for(k=0;k<count-1;k++)
	{
		i=Queue1.Display(k);

	    cout<<i<<' ';
	}
	cout<<m<<endl;

}