实验3.4 栈与队列——链队列

一、实验目的

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

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

二、实验内容

建立一个栈队列，实现队列的入队和出队操作。

三、实验源代码

#include <iostream>
using namespace std;
template<class DataType>
struct Node
{
	DataType data;
	Node<DataType>*next;
};
template <class DataType>
class LinkQueue
{
	public:
		LinkQueue();
		~LinkQueue();
		void EnQueue(DataType x);
		DataType DeQueue();
		DataType GetQueue();
		int Empty();
	private:
		Node<DataType>*front,*rear;
};

template <class DataType>
LinkQueue<DataType>::LinkQueue()
{
	Node<DataType> *s=NULL;
	s=new Node<DataType>;
	s->next=NULL;
	front=rear=s;
}
template <class DataType>
LinkQueue<DataType>::~LinkQueue()
{
	Node<DataType>*p=NULL;
	while(front!=NULL)
	{
		p=front->next;
		delete front;
		front=p;
	}
}
template <class DataType>
void LinkQueue<DataType>::EnQueue(DataType x)
{
	Node<DataType>*s=NULL;
	s=new Node<DataType>;
	s->data=x;
	s->next=NULL;
	rear->next=s;rear=s;
}

template <class DataType>
DataType LinkQueue<DataType>::DeQueue()
{
	Node<DataType>*p=NULL;
	int x;
	if(rear==front)throw"下溢";
	p=front->next;
	x=p->data;
	front->next=p->next;
	if(p->next==NULL)rear=front;
	delete p;
	return x;
}
template <class DataType>
DataType LinkQueue<DataType>::GetQueue()
{
	if(front!=rear)
		return front->next->data;
}

template <class DataType>
int LinkQueue<DataType>::Empty()
{
	if(front==rear)
		return 1;
	else
		return 0;
}

#include <iostream>
using namespace std;
void main()
{
	LinkQueue<int>Q;
	if(Q.Empty())
		cout<<"队列为空"<<endl;
	else
		cout<<"队列非空"<<endl;
	cout<<"元素10和15执行入队操作"<<endl;
	try
	{
		Q.EnQueue(10);
     	Q.EnQueue(15);
	}
	catch(char*wrong)
	{
		cout<<wrong<<endl;;
	}
	cout<<"查看对头元素：";
	cout<<Q.GetQueue()<<endl;
	cout<<"执行出队操作"<<endl;
	try
	{
		Q.DeQueue();
	}
	catch(char*wrong)
	{
		cout<<wrong<<endl;
	}
	cout<<"查看队头元素：";
	cout<<Q.GetQueue()<<endl;
}

四、实验结果截图

五、实验总结

（1）链队列基本操作的实现本质上也是单链表操作的简化，出析构函数外，算法的时间复杂度均为O(1)。

（2）链队列的结点可以复用单链表的结点。

（3）根据链栈进行修改，发现只需将链栈和顺序队列理解透彻，就能够很简单地做出链队列的各个函数。