数据结构之队列(循环队列、链队列的类模板实现)(C++)
程序员文章站
2022-05-04 16:24:32
...
一、循环队列类模板
//文件名:"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;
}
二、链队列类模板
//文件名:"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;
}
上一篇: ps制作逼真的水波效果