数据结构之链式栈(LinkedQueue)源代码

CLinkedNode.h文件

#pragma once
/*
*Copyright? 中国地质大学（武汉） 信息工程学院
*All right reserved.
*
*文件名称：CPolynomial.h
*摘    要：利用链表结构完成多项式的表示及其运算
*
*当前版本：1.0
*作       者：邵玉胜
*完成日期：2018-04-16
*/
 
#ifndef CLINKEDQUEUE
#define CLINKEDQUEUE
#include<iostream>
using namespace std;
 
template<class _Ty>
struct CLinkedNode{
	_Ty m_tData;
	CLinkedNode<_Ty>* m_pLink;
	CLinkedNode(_Ty data, CLinkedNode<_Ty>* next = nullptr) {
		m_tData = data;
		m_pLink = next;
	}
	CLinkedNode<_Ty>* InsertAfter(const _Ty data) {
		m_pLink = new CLinkedNode<_Ty>(data);
		if (m_pLink == nullptr) {
			cerr << "内存分配错误！" << endl;
			exit(-1);
		}
		return m_pLink;
	}
};
 
 
 
template<class _Ty>
class CLinkedQueue {
public:
	CLinkedQueue():m_pFront(nullptr), m_pRear(nullptr) {}      //构造函数，将头指针与尾指针都设为空
	CLinkedQueue(CLinkedQueue<_Ty>& Q);                        //赋值构造函数
	~CLinkedQueue();                                           //析构函数
	CLinkedQueue<_Ty>& operator = (CLinkedQueue<_Ty>& Q);      //重载赋值运算符
 
	void EnQueue(const _Ty data);                               //进队
	bool DeQueue(_Ty& data);                                    //出队
	bool GetFront(_Ty& data);                                   //获取队头值
	void MakeEmpty();                                           //置空函数
	bool IsEmpty();                                             //判空函数
	int  GetSize();                                             //获取队列大小
 
	//重载输入运算符
	//模板类的输入输出运算符的重载要写在类内种
 	friend istream& operator >> (istream& in, CLinkedQueue<_Ty>& Q) {
		cout << "请输入一个队列，输入\"#\"结束：";
		_Ty data;
		while (in >> data) {
			if (data == '#')
				break;
			else {
				Q.EnQueue(data);
			}
		}
		return in;
	}
	
	friend ostream& operator<<(ostream& out, CLinkedQueue<_Ty>& Q) {
		CLinkedNode<_Ty>* srcPtr = Q.GetHead();
		if (srcPtr == nullptr)
			out << "队列为空！" << endl;
		else {
			_Ty data;
			out << "队列中的元素为：";
			while (srcPtr != nullptr) {
				data = srcPtr->m_tData;
				out << data << " ";
				srcPtr = srcPtr->m_pLink;
			}
			out << endl;
		}
 
		return out;
	}
private:
	CLinkedNode<_Ty>* GetHead() { return m_pFront; }            //获取头指针
	CLinkedNode<_Ty>* m_pFront;                                 //头指针
	CLinkedNode<_Ty>* m_pRear;                                  //尾指针
};
 
//赋值构造函数
template<class _Ty>
CLinkedQueue<_Ty>::CLinkedQueue(CLinkedQueue<_Ty>& Q) {
	CLinkedNode<_Ty>* srcPtr = Q.GetHead();                     //指向参数第一个结点
	_Ty data;
	while (srcPtr != nullptr) {                                 //如果还未复制完
		data = srcPtr->m_tData;                                 //取出当前结点的数值
		this->EnQueue(data);                                    //将该数值到本对象
		srcPtr = srcPtr->m_pLink;                               //指向参数队列指向下一项
	}
}
 
//析构函数
template<class _Ty>
CLinkedQueue<_Ty>::~CLinkedQueue() {
	this->MakeEmpty();                                         //直接调用置空函数
}
 
//重载赋值运算符
template<class _Ty>
CLinkedQueue<_Ty>& CLinkedQueue<_Ty>::operator = (CLinkedQueue<_Ty>& Q) {
	CLinkedNode<_Ty>* srcPtr = Q.GetHead();                     //指向参数第一个结点
	_Ty data;
	while (srcPtr != nullptr) {                                 //如果还未复制完
		data = srcPtr->m_tData;                                 //取出当前结点的数值
		this->EnQueue(data);                                    //将该数值到本对象
		srcPtr = srcPtr->m_pLink;                               //指向参数队列指向下一项
	}
	return *this;
}
 
 
//进队
template<class _Ty>
void CLinkedQueue<_Ty>::EnQueue(const _Ty data) {
	if (m_pFront == nullptr) {                                     //如果队列为空
		m_pFront = m_pRear = new CLinkedNode<_Ty>(data);
		if (m_pFront == nullptr) {                                 //内存分配错误
			cerr << "内存分配错误！" << endl;
			exit(-1);
		}
	}
	else{                                                          //队列不为空
		m_pRear = m_pRear->InsertAfter(data);
		if (m_pRear == nullptr) {
			cerr << "内存分配错误！" << endl;
			exit(-1);
		}
	}
}
 
//出队
template<class _Ty>
bool CLinkedQueue<_Ty>::DeQueue(_Ty& data) {
	if (m_pFront == nullptr)                                     //如果队列为空，直接返回假
		return false;
	CLinkedNode<_Ty>* pfront = m_pFront;                        //定义一个临时变量指向头结点，用于释放空间
	data = pfront->m_tData;                                     //将头结点的值赋值给参数
	m_pFront = m_pFront->m_pLink;                               //指向头结点的下一结点
	delete pfront;                                              //释放原头结点的空间
	return true;
}
 
//获取队头值
template<class _Ty>
bool CLinkedQueue<_Ty>::GetFront(_Ty& data) {
	if (m_pFront == nullptr)                                   //如果队列为空，返回假
		return false;
	data = m_pFront->m_tData;                                  //用队头的值给data赋值
	return true;
}
 
//置空函数
template<class _Ty>
void CLinkedQueue<_Ty>::MakeEmpty() {
	CLinkedNode<_Ty>* pdel = nullptr;                            //指向删除结点
	while (m_pFront != nullptr) {                                //循环删除结点
		pdel = m_pFront;
		m_pFront = m_pFront->m_pLink;
		delete pdel;
	}
	m_pRear = nullptr;                                           //为安全起见，将m_pRear指向空
}
 
//判空函数
template<class _Ty>
bool CLinkedQueue<_Ty>::IsEmpty() {
	return m_pFront == nullptr;
}
 
//获取队列大小
template<class _Ty>
int  CLinkedQueue<_Ty>::GetSize() {
	CLinkedNode<_Ty>* pelement = m_pFront;                         //临时指针，指向队列元素
	int count = 0;                                                 //用于计数的临时变量，初始化为0
	while (pelement != nullptr) {                                  //当所指向的元素不为空时，说明没有到队尾指针
		++count;                                                   //计数加一
		pelement = pelement->m_pLink;                              //指向下一元素
	}
	return count;
}
 
#endif
 

main.cpp文件(测试文件)

#include"CLinkedQueue.h"
 
int main() {
	CLinkedQueue<int>* testQueue = new CLinkedQueue<int>();
	cin >> *testQueue;
	cout << *testQueue;
	int front;
	if (testQueue->DeQueue(front) == true) {
		cout << front << "出队" << endl;
		cout << "当前共有" << testQueue->GetSize() << "个元素" << endl;
		cout << *testQueue;
	}
	
	if (testQueue->GetFront(front) == true)
		cout << "当前的队头元素为：" << front << endl;
 
	CLinkedQueue<int>* copyQueue = new CLinkedQueue<int>(*testQueue);
	cout << "* copyQueue:" << endl;
	cout << *copyQueue;
 
 
	delete testQueue;
	return 0;
}