线性队列与链队列
用C++编程语言实现 线性队列与链队列 的代码撰写
一、顺序循环队列
#pragma once
#include <iostream>
using namespace std;
顺序队列类(class LinearQueue)
函数声明
//顺序循环队列
template<class T>
class LinearQueue
{
public:
LinearQueue(int LQMaxSize); //创建空队列
~LinearQueue(); //删除队列
bool IsEmpty(); //判断队列是否为空
bool IsFull(); //判断队列是否为满
bool Insert(const T& x); //入队，在队列尾部插入元素x
bool GetElement(T& x); //求对头元素的值放入x中
bool Delete(T& x); //出队，从对头删除一个元素，并将该元素的值放入x中
void OutPut(ostream& out)const; //输出队列
private:
int size; //队列实际元素个数
int front,rear; //队列的对头和队尾的指针
int MaxSize; //队列中最大元素个数
T* element; //一维动态数组
};
创建空队列
//创建空队列
template<class T>
LinearQueue<T>::LinearQueue(int LQMaxSize)
{
MaxSize = LQMaxSize;
element = new T[MaxSize];
size = 0;
front = 0;
rear = 0;
}
删除队列
//删除队列
template<class T>
LinearQueue<T>::~LinearQueue()
{
delete[] element;
}
判断队列是否为空
//判断队列是否为空
template<class T>
bool LinearQueue<T>::IsEmpty()
{
return size == 0;
}
判断队列是否为满
//判断队列是否为满
template<class T>
bool LinearQueue<T>::IsFull()
{
return size == MaxSize;
}
入队操作
//入队，在队列尾部插入元素x
template<class T>
bool LinearQueue<T>::Insert(const T& x)
{
if (IsFull())
return false;
element[rear] = x;
rear = (rear + 1) % (MaxSize);
size++;
return true;
}
求对头元素的值放入x中
//求对头元素的值放入x中
template<class T>
bool LinearQueue<T>::GetElement(T& x)
{
if (IsEmpty())
return false;
x = element[front];
return true;
}
出队操作
//出队，从对头删除一个元素，并将该元素的值放入x中
template<class T>
bool LinearQueue<T>::Delete(T& x)
{
if(IsEmpty())
return false;
x = element[front];
front = (front + 1) % (MaxSize);
size--;
return true;
}
输出队列及重载运算符<<
//输出队列
template<class T>
void LinearQueue<T>::OutPut(ostream& out)const
{
int index;
index = front;
for (int i = 0; i < size; i++)
{
out <<element[index] << endl;
index = (index + 1) % MaxSize;
}
}
//重载运算符<<
template<class T>
ostream& operator<<(ostream& out, const LinearQueue<T>& x)
{
x.OutPut(out);
return out;
}
主程序(main)
LinearQueue<int> q;
q.Insert(1);
q.Insert(2);
q.Insert(3);
cout << q;
二、链表队列
#pragma once
#include <iostream>
using namespace std;
单结点类(class Node)
template<class T>
class LinkNode
{
template<class T>
friend class LinkQueue;
public:
LinkNode()
{
next = nullptr;
}
private:
T data; //结点元素
LinkNode<T>* next; //指向下一个结点的指针
};
链接队列类（class LinkList)
函数声明
//链接队列
template<class T>
class LinkQueue
{
public:
LinkQueue(); //创建空队列
~LinkQueue(); //删除队列
bool IsEmpty(); //判断队列是否为空
bool Insert(const T& x); //入队，在队列尾部插入元素x
bool GetElement(T& x); //求对头元素的值放入x中
bool Delete(T& x); //出队，从对头删除一个元素，并将该元素的值放入x中
void OutPut(ostream& out)const; //输出队列
private:
int size; //队列实际元素个数
LinkNode<T>* front, * rear; //队列的对头和队尾的指针
};
创建链表(析构函数)
//创建空队列
template<class T>
LinkQueue<T>::LinkQueue()
{
front = NULL;
rear = NULL;
size = 0;
}
删除链表(析构函数)
//删除队列
template<class T>
LinkQueue<T>::~LinkQueue()
{
T x;
while (front != NULL)
{
Delete(x);
}
}
判断链表是否为空
//判断队列是否为空
template<class T>
bool LinkQueue<T>::IsEmpty()
{
return size == 0;
}
入队操作
//入队，在队列尾部插入元素x
template<class T>
bool LinkQueue<T>::Insert(const T& x)
{
LinkNode<T>* p = new LinkNode<T>;
if (p == NULL)
return false;
p->data = x; //为元素赋值
if (front == NULL) //插入前是空队列
{
rear = p;
front = p;
}
else
{
rear->next = p; //插入新结点
rear = p; //指向新队列
}
size++;
return true;
}
求对头元素的值放入x中
//求对头元素的值放入x中
template<class T>
bool LinkQueue<T>::GetElement(T& x)
{
if (IsEmpty())
return false;
x = front->data;
return true;
}
出队操作
//出队，从对头删除一个元素，并将该元素的值放入x中
template<class T>
bool LinkQueue<T>::Delete(T& x)
{
LinkNode<T>* p;
if(IsEmpty())
return false;
p = front;
x = front->data;
front = front->next;
delete p; //删除队头结点
size--;
return true;
}
输出队列及重载运算符<<
//输出队列
template<class T>
void LinkQueue<T>::OutPut(ostream& out)const
{
LinkNode<T>* p;
p = front;
for (int i = 0; i < size; i++)
{
out << p->data << endl;
p = p->next;
}
}
//重载运算符<<
template<class T>
ostream& operator<<(ostream& out, const LinkQueue<T>& x)
{
x.OutPut(out);
return out;
}
主程序(main)
LinkQueue<int> q;
q.Insert(1);
q.Insert(2);
q.Insert(3);
cout << q;
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
