lianshiduilie.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<Type>
      *l = NULL ) : data (d), link (l) { }
};  
template <class Type> class Queue {	
private: 
    QueueNode<Type> *front, *rear,*p1;   
                                   //队头、队尾指针
public: 
    Queue ( ) : rear ( NULL ), front ( NULL ) { }
    ~Queue ( );						
    void EnQueue ( const Type & item );
    Type DeQueue ( );					
    Type GetFront ( );					
    void MakeEmpty ( );  //实现与~Queue( )同
     int IsEmpty ( ) const
                    { return front == NULL; }	
	 void Create(Type a[],int n)
			{
   QueueNode<Type> *q;

	p1=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 p1;
			QueueNode<Type> *q=p1->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==p1)
				return NULL;
			else return q->data;
		}
};
          
template <class Type>
Queue<Type> :: ~Queue ( ) {
//队列的析构函数
    QueueNode<Type> *p;
    while ( front != NULL ) {   //逐个结点释放
        p = front;  front = front->link;  delete p;
    }
}
template <class Type> 
void Queue<Type> :: 
EnQueue ( const Type& item ) {
//将新元素item插入到队列的队尾 
    if ( front == NULL )    //创建第一个结点
	front = rear = new QueueNode
		<Type> ( item, NULL );
    else                               //队列不空, 插入
         rear = rear->link = new QueueNode
		<Type> ( item, NULL );
}
template <class Type> 
Type Queue<Type> :: DeQueue ( ) {
    assert(!IsEmpty());     //判队空
    QueueNode<Type> *p = front;
   Type  retvalue=p->data;		
    front = front->link;   delete p; 
    return retvalue;				
}
template <class Type> 
Type *Queue<Type> :: GetFront ( ) {
    assert(!IsEmpty());	
    return front->data;
} 
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;

}