先进先出的数据结构-----队列（基于链表）

#pragma once
const int maxSize = 50;

template
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 "Queue.h"

template
struct ListNode {
	T data;
	ListNode *next;
	ListNode(const T& data, ListNode *next = nullptr) {
		this->data = data;
		this->next = next;
	}

	ListNode(ListNode *next = nullptr) {
		this->next = next;
	}
};

template
class linkedQueue:public Queue
{
public:
	linkedQueue():rear(nullptr),front(nullptr){}
	~linkedQueue() { makeEmpty(); }
	void makeEmpty();
	bool EnQueue(const T& x);   //新元素进队列
	bool DeQueue(T& x);         //队头元素出队列
	bool getFront(T& x);        //获得队头元素
	bool IsEmpty()const { return (nullptr == front) ? true : false; }            //判断队列是否为空
	bool IsFull() const { return false; }				//判断队列是否为满
	int getSize() const;								//获取队列中元素个数

	//重载输出符
	friend ostream& operator<<(ostream& os, linkedQueue& lq) {
		os << "队列中元素个数： " << lq.getSize() << endl;
		ListNode *p = lq.front;
		int i = 0;
		while (p != nullptr) {
			os << ++i << ": " << p->data << endl;
			p = p->next;
		}
		return os;
	}

private:
	ListNode *front, *rear;
};

template
void linkedQueue::makeEmpty()
{
	//置空链表，释放所有结点
	ListNode *p;
	while (front != nullptr) {
		p = front;
		front = front->next;
		delete p;
	}
}

template
bool linkedQueue::EnQueue(const T & x)
{
	//将新元素x插入到队列的队尾

	//空队列时，新结点成为队列的第一个结点，既是队头，也是队尾
	if (front == nullptr) {
		front = rear = new ListNode(x);
		if (front == nullptr) {
			cout << "分配内存失败！";
			return false;
		}
	}
	else {
		//非空队列，在队尾追加新的结点，并更新队尾
		rear->next = new ListNode(x);
		if (rear->next == nullptr) {
			cout << "分配内存失败！";
			return false;
		}
		rear = rear->next;
	}
	return true;
}

template
bool linkedQueue::DeQueue(T & x)
{
	//如果队列不为空，将队头结点删除
	if (IsEmpty() == true) {
		return false;
	}

	ListNode *p = front;
	x = p->data;
	front = front->next;
	delete p;
	return true;
}

template
bool linkedQueue::getFront(T & x)
{
	//如果队列不为空，返回结点值
	if (IsEmpty() == true) {
		return false;
	}

	x = front->data;
	return true;
}

template
int linkedQueue::getSize() const
{
	ListNode *p = front;
	int count = 0;
	while (p != nullptr) {
		p = p->next;
		count++;
	}
	return count;
}