实验三链队列

一、实验目的

1、   熟练掌栈和队列的结构特点，掌握栈和队列的顺序存储和链式存储结构和实现。

2、      学会使用栈和队列解决实际问题。

二、实验内容

1、自己确定结点的具体数据类型和问题规模：

分别建立一个顺序栈和链栈，实现栈的压栈和出栈操作。

分别建立一个顺序队列和链队列，实现队列的入队和出队操作。

#include<iostream>
using namespace std;
template<typename T>
struct Node
{
	T data;
	Node<T>*next;
};
template<typename T>
class LinkQueue
{
	public:
		LinkQueue();//初始化一个空的链栈
		~LinkQueue();
		void EnQueue(T x);//入列
		T DeQueue();//队头元素出列
		T GetQueue();//取链队列的头元素
		int Empty();//判断链队列是否为空
	private:
		Node<T>*front,*rear;//队头和队尾指针
};
template<class T>
LinkQueue<T>::LinkQueue()
{
	Node<T>*s=NULL;
	s=new Node<T>;
	s->next=NULL;
	front=rear=s;
}
template<typename T>
LinkQueue<T>::~LinkQueue()
{
	Node<T>*p=NULL;
	while(front!=NULL)
	{
		p=front->next;
		delete front;
		front=p;
	}
}
template<typename T>
void LinkQueue<T>::EnQueue(T x)
{
	Node<T>*s=NULL;
	s=new Node<T>;
	s->data=x;//数据域为x的节点s
	s->next=NULL;
	rear->next=s;
	rear=s;//将节点s插入到队尾
}
template<typename T>
T LinkQueue<T>::DeQueue()
{
	Node<T>*p=NULL;
	int x;
	if(rear==front)throw"下溢";
	p=front->next;
	x=p->data;//暂存队头元素
	front->next=p->next;//将队头元素所在节点摘链
	if(p->next==NULL)rear=front;//判断出队前队列长是否为1
	delete p;
	return x;
}
template<typename T>
T LinkQueue<T>::GetQueue()
{
	if(front!=rear)
		return front->next->data;
}
template<class T>
int LinkQueue<T>::Empty()
{
	if(front==rear)
		return 1;
	else 
		return 0;
}
void main()
{
	LinkQueue<int>Q;
	if(Q.Empty())
		cout<<"队列为空"<<endl;
	else
		cout<<"队列非空"<<endl;
	cout<<"元素1和2入列"<<endl;
	try
	{
		Q.EnQueue(1);
		Q.EnQueue(2);
	}
	catch(char*wrong)
	{
		cout<<wrong<<endl;
	}
	cout<<"查看队头元素"<<endl;
	cout<<"执行出队操作"<<endl;
	try
	{
		Q.DeQueue();
	}
	catch(char*wrong)
	{
		cout<<wrong<<endl;
	}
	cout<<"查看队头元素"<<endl;
	cout<<Q.GetQueue()<<endl;
}