数据结构--链队列C++(模板类实现)
作者:
AmbitionX
,
2022-05-03 19:35:48
,
所有人可见
,
阅读 278
#include <iostream>
using namespace std;
template <typename DataType>
struct Node
{
DataType data;
Node<DataType> *next;
};
template <typename DataType>
class LinkQueue
{
public:
LinkQueue( ); //构造函数,初始化一个空的链队列
~LinkQueue( ); //析构函数,释放链队列中各结点的存储空间
void EnQueue(DataType x); //将元素x入队
DataType DeQueue( ); //将队头元素出队
DataType GetHead( ); //取链队列的队头元素
void Empty( ); //判断链队列是否为空
private:
Node<DataType> *front, *rear; //队头和队尾指针,分别指向头结点和终端结点
};
// 初始化
template <typename DataType>
LinkQueue<DataType>::LinkQueue( )
{
Node <DataType> *s;
s = new Node<DataType>;
s->next = NULL;
front = rear = s;
}
// 析构函数 链队的销毁
template <typename DataType>
LinkQueue<DataType>::~LinkQueue( )
{
Node <DataType> *p;
while(front != NULL)
{
p = front->next;
delete front;
front = p;
}
}
// 入队操作
template <typename DataType>
void LinkQueue<DataType>:: EnQueue(DataType x)
{
Node<DataType> * s = nullptr;
s = new Node<DataType>;
s->data = x; // 将节点s插入到队尾
s->next = nullptr;
rear->next = s;
rear = s;
}
// 出队操作
template <typename DataType>
DataType LinkQueue<DataType>:: DeQueue()
{
DataType x;
Node<DataType> * p = nullptr;
if (rear == front) throw "下溢";
p = front->next;
x = p->data; // 暂存对头元素
front->next = p->next; // 对头元素所在结点摘链
if (p->next == nullptr) rear = front; // 出对前队列长度为1时候,要特殊考虑
delete p;
return x;
}
// 取对头操作
template <typename DataType>
DataType LinkQueue<DataType>:: GetHead()
{
return front->next->data;
}
// 判空操作
template <typename DataType>
void LinkQueue<DataType>:: Empty()
{
if (front == rear) cout << "为空" << endl;
else cout << "不空" << endl;
}
int main()
{
LinkQueue<int> Q; //创建模版类的实例
Q.Empty();
cout<<"元素10和15执行入队操作:"<<endl;
try
{
Q.EnQueue(10); //入队操作
Q.EnQueue(15);
}
catch (char* wrong)
{
cout<<wrong<<endl;;
}
cout<<"查看队头元素:"<<endl;
cout<<Q.GetHead( )<<endl; //读队头元素
cout<<"执行出队操作:"<<endl; //出队操作
try
{
Q.DeQueue( );
}
catch (char* wrong)
{
cout<<wrong<<endl;
}
cout<<"查看队头元素:"<<endl;
cout<<Q.GetHead( )<<endl;
return 0;
}