shiyan4.cpp

队列

#include <assert.h>
#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;
    int rear, front,tag;			//队尾, 队头指针
    Type *elements; 	         //队列元素数组	
    int maxSize;                    //最大元素个数
public: 
     Queue ( int = 10 );
     ~Queue ( ) { delete [ ] elements; }
     void EnQueue ( const Type & item); //进队
    Type DeQueue ( );            //退队
    Type GetFront ( );       //取队头元素
    void MakeEmpty ( ) { front = rear =tag= 0; }
    int IsEmpty ( ) const 
       { return front == rear&&tag==0; }
    int IsFull ( ) const
       { return front==rear&&tag==1; }
    //int Length ( ) const
     //  { return (rear-front+maxSize) % maxSize;}
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 ( int sz ) : 
front (0), rear (0), tag(0),maxSize (sz) {
    elements = new Type[maxSize];		
    assert ( elements != NULL );
}


template <class Type> void Queue<Type>::
EnQueue ( const Type & item ) {
     assert ( !IsFull ( ) ); 
     rear = (rear+1) % maxSize;			
     elements[rear] = item;	
	 tag=1;
}
template <class Type>Type Queue<Type> :: DeQueue ( ) {
     assert(!IsEmpty()); 	
     front = ( front+1) % maxSize;
	 tag=0;
     return elements[front];
}

template <class Type>Type Queue<Type> :: GetFront ( ) {
     assert ( !IsEmpty ( ) );				
     return elements[( front+1) % MaxSize];
}
 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;
	 cout<<"经过进队算法后得到的队列为：";
	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=1;k<count;k++)
	{
		i=Queue1.Display(k);

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

 }