[数据结构与算法]先进先出的数据结构--------队列（基于数组）

队列是一种限定存取位置的线性表，只允许在表的一段插入，在另一端删除

队列的存储表示也有两种，一种是基于数组，一种是基于链表
1、基于数组的队列会出现假溢出的情况，由于队列特性会导致数组前端可能还有空位置。

使用循环队列解决上述问题

使用基于数组的循环队列，首尾相接，当队头指针front和队尾指针rear进到maxSize-1后，再前进一个一个位置就自动到0。这可以利用除法求余的运算来实现：

队头的指针进1：front = （front + 1）% maxSize；
队尾的指针进1：rear = （rear + 1）% maxSize；
循环队列的队头指针和队尾指针初始化都为0：front = rear = 0。在队尾插入新元素和删除队头元素时，两个指针都按顺时针方向进1，当它们到maxSize - 1时，并不表示终结，利用%运算前进到数组的0号位置。
为了区别队空条件，用（rear + 1）%maxSize == front 来判断是否队已满。

队列的抽象定义：

#pragma once
const int maxSize = 50;

template<class T>
class Queue
{
public:
	Queue() {};
	~Queue() {};
	virtual bool EnQueue(const T& x) = 0;   //新元素进队列
	virtual bool DeQueue(T& x) = 0;         //队头元素出队列
	virtual bool getFront(T& x) = 0;        //获得队头元素
	virtual bool IsEmpty()const = 0;             //判断队列是否为空
	virtual bool IsFull() const= 0;				//判断队列是否为满
	virtual int getSize() const= 0;
};

循环队列定义及实现：

#pragma once
#include <iostream>
#include "Queue.h"
using namespace std;


template<class T>
class SeqQueue:public Queue<T>
{
public:
	SeqQueue(int sz = 10);
	~SeqQueue() { delete[] elements; }
	
	//队列不为满，则x进队列，否则溢出处理
	bool EnQueue(const T& x);

	//队列不为空，退出并返回队列头元素
	bool DeQueue(T& x);

	//队列不为空， 获取队列头元素
	bool getFront(T& x);

	//置空操作，rear = front = 0
	void makeEmpty() { rear = front = 0; }

	//判断队列是否为空 rear == front
	bool IsEmpty()const { return (rear == front) ? true : false; }

	//判断队列是否为满 （rear + 1）% maxSize == front
	bool IsFull()const { return (rear + 1) % maxSize == front ? true : false; }

	//获取队列实际元素个数
	int getSize()const { return (rear - front + maxSize) % maxSize; }

	//重载输出符
	friend ostream& operator<<(ostream& os, SeqQueue<T>& sq) {
		os << "front = " << sq.front << ", rear = " << sq.rear << endl;
		for (int i = sq.front; i != sq.rear; i = (i + 1) % sq.maxSize) {
			os << i << ": " << sq.elements[i] << endl;
		}
		return os;
	}

private:
	T* elements;
	int rear, front;
	int maxSize;
};

template<class T>
SeqQueue<T>::SeqQueue(int sz)
{
	rear = front = 0;
	maxSize = sz;
	elements = new T[maxSize];
	if (elements == nullptr) {
		cout << "分配内存失败！" << endl;
	}
}

template<class T>
bool SeqQueue<T>::EnQueue(const T & x)
{
	if (IsFull() == true) {
		cout << "队列已满";
		return false;
	}
	elements[rear] = x;
	rear = (rear + 1) % maxSize;
	return true;
}

template<class T>
bool SeqQueue<T>::DeQueue(T& x) {
	if (IsEmpty() == true) {
		cout << "队列为空！";
		return false;
	}
	x = elements[front];
	front = (front + 1) % maxSize;
	return true;
}

template<class T>
bool SeqQueue<T>::getFront(T & x)
{
	if (IsEmpty() == true) {
		cout << "队列为空！";
		return false;
	}
	x = elements[front];
	return true;
}

测试用例：

int main()
{
	SeqQueue<int> sq;

	if (sq.IsEmpty() == true) {
		cout << "队列为空！" << endl;
	}

	sq.EnQueue(4);
	sq.EnQueue(5);
	sq.EnQueue(6);
	sq.EnQueue(7);
	sq.EnQueue(8);
	sq.EnQueue(9);
	sq.EnQueue(10);
	sq.EnQueue(11);
	sq.EnQueue(12);

	cout << sq << endl;
	
	int x = 0;
	sq.DeQueue(x);
	sq.DeQueue(x);
	sq.DeQueue(x);
	sq.DeQueue(x);
	sq.DeQueue(x);

	cout << sq << endl;
	
	sq.EnQueue(10);
	sq.EnQueue(11);
	sq.EnQueue(12);
	sq.EnQueue(13);

	cout << sq << endl;

	system("pause");
    return 0;
}