[数据结构与算法]C++实现队列的顺序存储和链式存储

1、队列定义（逻辑结构）

队列是一种只允许在表的一端进行插入，另一端进行删除操作的线性表。这是一种受限的线性表，满足先进先出的原则（FIFO），允许入队的一端称为队尾（rear），允许出队的一端称为队头（front）。

2、队列的顺序存储（物理结构）

定义两个整型变量头指针front和尾指针rear
约定front始终指向队头元素，rear指向队尾元素的下一个位置，可知队列为空的条件是front == rear。但引出一个问题，当队列中插满元素之后再全部出队，此时front == rear，造成下标溢出，不能再进行下一次入队操作。这里引入第三个变量size，在size = 0前提下front == rear则为空队列。否则当队列满时，不能进行入队操作。
设计时，数组的头指针和尾指针谁放队头队尾都差不多

#pragma once
#pragma once
#include<iostream>
using namespace std;

template<class T>
class LinerQueue
{
public:
	LinerQueue(int LQMaxSize);		//创建空队列
	~LinerQueue();					//删除队列

	bool IsEmpty();				//判断队列是否为空
	bool IsFull();				//判断队列是否为满
	
	bool Insert(const T& x);		//进队操作，在队尾插入元素x，插入成功返回true
	bool GetElement(T& x);			//求队头元素的值，并放入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>
LinerQueue<T>::LinerQueue(int LQMaxSize)
{
	MaxSize = LQMaxSize;
	element = new T[LQMaxSize];	//开辟堆空间
	size = 0;
	front = rear = 0;
}

template<class T>
LinerQueue<T>::~LinerQueue()
{
	delete[] element;
}


template<class T>
bool LinerQueue<T>::IsEmpty()
{
	return size == 0;
}

template<class T>
bool LinerQueue<T>::IsFull()
{
	return size == MaxSize;
}


template<class T>
bool LinerQueue<T>::Insert(const T& x)	//入队是操作rear
{
	if (IsFull())		//满队列返回false
		return false;
	else
	{
		element[rear] = x;
		rear = (rear + 1) % MaxSize;	//逻辑上使队列成为循环队列，防止下标溢出
		size++;
		return true;
	}
}

template<class T>
bool LinerQueue<T>::GetElement(T& x)
{
	if (IsEmpty())		//空队列返回false
		return false;
	else
	{
		x = element[front];
		return true;
	}
}

template<class T>
bool LinerQueue<T>::Delete(T& x)		//出队操作front
{
	if (IsEmpty())		//空队列返回false
		return false;
	else
	{
		x = element[front];
		front = (front + 1) % MaxSize;	//逻辑上使队列成为循环队列
		size--;
		return true;
	}
}

template<class T>
void LinerQueue<T>::OutPut(ostream& out) const
{
	int 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 LinerQueue<T>& x)
{
	x.OutPut(out);
	return out;
}

3、队列的链式存储（物理结构）

约定front指向队头元素，rear指向队尾元素。

#pragma once
#pragma once
#include<iostream>
using namespace std;

template<class T>
class LinkNode
{
	template<class T>
	friend class LinkQueue;
public:
	LinkNode()			//构造函数
	{
		next = NULL;
	}					//每new一个结点时，先将他置空，串进链表之后才设next
private:
	T data;
	LinkNode<T>* next;
};

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:
	LinkNode<T> *front, *rear;		//指向队头、队尾指针

	int size;			//栈中元素个数
};

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;
}

template<class T>
bool LinkQueue<T>::Insert(const T& x)		//这里x只是数据域
{
	LinkNode<T>* p = new LinkNode<T>;	//新建结点用于标记新插入的元素
	if (p == NULL)
		return false;
	else
	{
		p->data = x;
		if (front == NULL)	//空队列，所以插入的只有一个元素，此时rear指向队尾还是p
		{
			rear = p;
			front = p;
		}
		else
		{
			rear->next = p;
			rear = p;
		}
		size++;
		return true;
	}
}

template<class T>
bool LinkQueue<T>::GetElement(T& x)
{
	if (IsEmpty())		//空栈返回false
		return false;
	else
	{
		x = front->data;
		return true;
	}
}

template<class T>
bool LinkQueue<T>::Delete(T& x)
{
	LinkNode<T>* p;			//记录待删除的结点(头结点)
	if (IsEmpty())			//空栈返回false
		return false;
	else
	{
		p = front;
		x = front->data;
		front = front->next;
		size--;
		delete p;
		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;
}

4、测试

新建test.cpp文件

#include<iostream>
using namespace std;
#include"LinerQueue.h"
#include"LinkQueue.h"
int main()
{
	//LinerQueue<int> s(5);
	LinkQueue<int> s;
	s.Insert(1);
	s.Insert(2);
	s.Insert(3);
	s.Insert(4);
	s.Insert(5);

	int x;
	s.Delete(x);
	cout << x << endl;

	s.GetElement(x);
	cout << x << endl;

	return 0;
}