欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构之队列(循环队列、链队列的类模板实现)(C++)

程序员文章站 2022-05-04 16:24:32
...

一、循环队列类模板
数据结构之队列(循环队列、链队列的类模板实现)(C++)

//文件名:"CQueue.h"
#pragma once
#ifndef CQUEUE_H_
#define CQUEUE_H_

/*
	顺序队列之循环队列 类模板定义 CQueue (Cycle Queue) 
*/

template <typename ElemType>
class CQueue
{
private:
	ElemType **base;	//指针的指针(一维指针数组),队列存储空间基址
	int front;	//队头索引
	int rear;	//队尾索引
	int QueueSize;	//队列容量
public:
	CQueue(int m);	//有参构造
	~CQueue();	//析构函数:销毁队列
	void EnQueue(ElemType *e);	//入队
	ElemType *DeQueue();	//出队
	ElemType *GetHead();	//获取队头元素
	ElemType *GetLast();	//获取队尾元素
	bool isEmpty();	//判断是否队空
	bool isFull();	//判断是否队满
	//void Display();	//显示队列------需元素对象自身先实现 Display() 接口
};

template <typename ElemType>
CQueue<ElemType>::CQueue(int m)
{
	/*
		有参构造
	*/
	//1.初始化队列指针数组
	this->base = (ElemType **)malloc((m + 1) * sizeof(ElemType *));	//由于队尾有一个元素位置留空,用来区分队空队满,故多设一个空间
	//2.初始状态:队头队尾指向 下标索引 0
	this->front = 0;
	this->rear = 0;
	//3.队列容量
	this->QueueSize = m + 1;
}

template <typename ElemType>
CQueue<ElemType>::~CQueue()
{
	/*
		析构函数:销毁队列
		注:仅销毁一维指针数组,不销毁元素对象
	*/
	if (this->base == NULL)
	{
		return;
	}
	delete[] this->base;
	cout << "队列已销毁!" << endl;
}

template <typename ElemType>
void CQueue<ElemType>::EnQueue(ElemType *e)
{
	/*
		入队
	*/
	//1.入队前队满判断
	if (isFull())
	{
		cout << "队满!不可入队。" << endl;
		return;
	}
	//2.队尾赋值
	*(this->base + this->rear) = e;
	//3.队尾后移+1
	this->rear = (this->rear + 1) % this->QueueSize;	//----对队长取余 % ,可以实现下标索引循环
}

template <typename ElemType>
ElemType *CQueue<ElemType>::DeQueue()
{
	/*
		出队
	*/
	//1.出队前队空判断
	if (isEmpty())
	{
		cout << "队空!无法出队。" << endl;
		return NULL;
	}
	//2.取队头元素出队
	ElemType *e = *(this->base + this->front);
	//3.队头后移+1
	this->front = (this->front + 1) % this->QueueSize;	//----对队长取余 % ,可以实现下标索引循环
	return e;
}

template <typename ElemType>
ElemType *CQueue<ElemType>::GetHead()
{
	/*
		取队头元素
	*/
	//1.取队头元素前,判断队空
	if (isEmpty())
	{
		cout << "队空!无队头元素。" << endl;
		return NULL;
	}
	//2.取队头元素
	return *(this->base + this->front);
}

template <typename ElemType>
ElemType *CQueue<ElemType>::GetLast()
{
	/*
		取队尾元素
	*/
	//1.取队尾元素前,判断队空
	if (isEmpty())
	{
		cout << "队空!无队尾元素。" << endl;
		return NULL;
	}
	//2.取队尾元素,rear 前移减 1 :(rear - 1 + QueueSize) % QueueSize
	return *(this->base + (this->rear - 1 + this->QueueSize) % this->QueueSize);
}

template <typename ElemType>
bool CQueue<ElemType>::isEmpty()
{
	/*
		判断是否队空
			条件:rear == fornt
	*/
	return this->rear == this->front ? true : false;
}

template <typename ElemType>
bool CQueue<ElemType>::isFull()
{
	/*
		判断是否队满
			条件:(rear + 1) % QueueSize == front	---- 对队长取余 % ,可以实现下标索引循环
			注:需入队前判断
	*/
	return (this->rear + 1) % this->QueueSize == this->front ? true : false;
}

#endif // !CQUEUE_H_
//文件名:"CQueue_Test.cpp"
#include "stdafx.h"
#include <iostream>
#include "CQueue.h"
using namespace std;

struct Node
{
	int a;
	int b;
};

int main()
{
	Node n1{ 1,1 };
	Node n2{ 2,2 };
	Node n3{ 3,3 };
	Node n4{ 4,4 };
	CQueue<Node> *qa = new CQueue<Node>(3);
	qa->DeQueue();	//队空测试
	qa->EnQueue(&n1);
	qa->EnQueue(&n2);
	qa->EnQueue(&n3);
	qa->EnQueue(&n4);	//队满测试
	cout << "队头:" << (*qa->GetHead()).a << endl;	//队头测试
	cout << "队尾:" << (*qa->GetLast()).a << endl;	//队尾测试
	cout << "出队元素:" << (*qa->DeQueue()).a << endl;	//出队元素测试
	qa->EnQueue(&n4);	//再入队测试
	qa->EnQueue(&n1);	//再满队测试
	cout << "出队元素:" << (*qa->DeQueue()).a << endl;	//出队元素测试
	cout << "出队元素:" << (*qa->DeQueue()).a << endl;	//出队元素测试
	cout << "出队元素:" << (*qa->DeQueue()).a << endl;	//出队元素测试
	qa->DeQueue();	//清空队列后,队空测试
	qa->EnQueue(&n1);	//清空队列后,再入队测试
	qa->EnQueue(&n2);	//再入队测试
	cout << "队头:" << (*qa->GetHead()).a << endl;	//队头测试
	cout << "队尾:" << (*qa->GetLast()).a << endl;	//队尾测试
	delete qa;	//队列销毁测试
	
	return 0;
}


二、链队列类模板
数据结构之队列(循环队列、链队列的类模板实现)(C++)

//文件名:"LinkQueue.h"
#pragma once
#ifndef LINKQUEUE_H_
#define LINKQUEUE_H_

/*
	链队列 类模板定义	LinkQueue (Linked Queue)
		注:采用链尾插入法时,需添加一个头结点,以使后续入队元素操作一致
*/

template <typename ElemType>
class LinkQueue
{
	/*
		链队列
	*/
	struct Node
	{
		ElemType *data;
		Node *next;
	};
private:
	Node * front;	//队头指针
	Node * rear;	//队尾指针
public:
	LinkQueue();	//无参构造
	~LinkQueue();	//析构函数:销毁链队
	void EnQueue(ElemType *e);	//入队
	ElemType *DeQueue();	//出队
	ElemType *GetHead();	//获取队头元素
	ElemType *GetLast();	//获取队尾元素
	//void Display();	//显示队列元素
};

template <typename ElemType>
LinkQueue<ElemType>::LinkQueue()
{
	/*
		无参构造
	*/
	//1.建立头结点
	Node *p = new Node;
	p->next = NULL;
	//2.队头队尾指针指向头结点
	this->rear = p;
	this->front = this->rear;
}

template <typename ElemType>
LinkQueue<ElemType>::~LinkQueue()
{
	/*
		析构函数:销毁队列
			注:采用链头删除法
	*/
	Node *p;
	//从front 头结点遍历到链尾
	int i = 0;
	while (this->front != NULL)	//条件:尾结点 next == NULL
	{
		p = this->front;
		this->front = this->front->next;
		delete p;
		i++;
	}
	cout << "共销毁结点:" << i - 1 << "个。" << endl;	//计数时,去除头结点
}

template <typename ElemType>
void LinkQueue<ElemType>::EnQueue(ElemType *e)
{
	/*
		入队
	*/
	//1.建立入队结点
	Node *p = new Node;
	p->data = e;
	p->next = NULL;
	this->rear->next = p;
	//2.队尾指针后移至入队结点
	this->rear = p;
}

template <typename ElemType>
ElemType *LinkQueue<ElemType>::DeQueue()
{
	/*
		出队
	*/
	//1.空队列判断
	if (this->front == this->rear)
	{
		cout << "空队列!不可出队。" << endl;
		return NULL;
	}
	//2.非空队时,取队头元素结点
	Node *p = this->front->next;
	ElemType *e = p->data;
	//3.移除队头元素结点
	this->front->next = p->next;
	delete p;
	//4.若头结点 next 域为空,即无元素结点,此时将 rear = front
	if (this->front->next == NULL)
	{
		this->rear = this->front;
	}
	return e;
}

template <typename ElemType>
ElemType *LinkQueue<ElemType>::GetHead()
{
	/*
		取队头
	*/
	//1.空队列判断
	if (this->front == this->rear)
	{
		cout << "空队列!无队头。" << endl;
		return NULL;
	}
	//2.非空队时,取队头元素结点
	return this->front->next->data;
}

template <typename ElemType>
ElemType *LinkQueue<ElemType>::GetLast()
{
	/*
		取队尾
	*/
	//1.空队列判断
	if (this->front == this->rear)
	{
		cout << "空队列!无队尾。" << endl;
		return NULL;
	}
	//2.非空队时,取队尾元素结点
	return this->rear->data;
}

#endif // !LINKQUEUE_H_
//文件名:"LinkQueue_Test"
#include "stdafx.h"
#include <iostream>
#include "LinkQueue.h"
using namespace std;

struct Node
{
	int a;
	int b;
};

int main()
{
	Node n1{ 1,1 };
	Node n2{ 2,2 };
	Node n3{ 3,3 };
	Node n4{ 4,4 };
	LinkQueue<Node> *qa = new LinkQueue<Node>;
	qa->DeQueue();	//队空测试
	qa->EnQueue(&n1);
	qa->EnQueue(&n2);
	qa->EnQueue(&n3);
	cout << "队头:" << (*qa->GetHead()).a << endl;	//队头测试
	cout << "队尾:" << (*qa->GetLast()).a << endl;	//队尾测试
	cout << "出队元素:" << (*qa->DeQueue()).a << endl;	//出队元素测试
	qa->EnQueue(&n4);	//再入队测试
	cout << "队头:" << (*qa->GetHead()).a << endl;	//队头测试
	cout << "队尾:" << (*qa->GetLast()).a << endl;	//队尾测试
	cout << "出队元素:" << (*qa->DeQueue()).a << endl;	//出队元素测试
	cout << "出队元素:" << (*qa->DeQueue()).a << endl;	//出队元素测试
	cout << "出队元素:" << (*qa->DeQueue()).a << endl;	//出队元素测试
	qa->DeQueue();	//清空队列后,队空测试
	qa->EnQueue(&n1);	//清空队列后,再入队测试
	cout << "队头:" << (*qa->GetHead()).a << endl;	//队头测试
	cout << "队尾:" << (*qa->GetLast()).a << endl;	//队尾测试
	delete qa;	//队列销毁测试
	
	return 0;
}