数据结构C++队列（数组，链表）

#include
using namespace std;

//队列（课本版）

//老祖宗
template
class queue {
public:
	virtual ~queue(){}

	virtual bool empty()const = 0;//队列为空时返回true，否则返回false
	virtual int size()const = 0;//返回队列中元素个数

	virtual T& front() = 0;//返回队列中头元素
	virtual T& back() = 0;//返回队列尾元素

	virtual void pop() = 0;//队列头元素
    virtual void push(const T& theElement) = 0;//将元素theElement加入队尾
};

//循环队列
template
class arrayQueue :public queue
{
public:
	//构造函数
	arrayQueue(int initialCapacity = 10);
	~arrayQueue() { delete[] queue; }

	bool empty()const { return queueFront == queueBack; }
	int size()const
	{
		return (arrayLength + queueBack - queueFront) % arrayLength;
	}
	T& front()const;//返回队首元素
	T& back()const;//返回队尾元素
	void pop();//删除队首元素
	void push(const T& theElement);//元素插到队尾
private:
	int queueFront;//与第一个元素在反时针方向上相差一个位置
	int queueBack;//指向最后一个元素
	int arrayLength;//队列数组容量
	T* queue;//元素数组(灵魂)
};

template
arrayQueue::arrayQueue(int initialCapacity)
{
	//构造函数
	if (initialCapacity < 1)
	{
		//输出错误信息，抛出异常
		arrayLength = initialCapacity;
		queue = new T[arrayLength];
		queueFront = queueBack = 0;
	}
}
template
T& arrayQueue::front()const
{
	//返回队首元素
	if (queueFront == queueBack)throw QueueEmpty();  //队空，就不能拿回来队首
	return queue[(queueFront + 1) % arrayLength];
}

template
T& arrayQueue::back()const
{
	//返回队尾元素
	if (queueFront == queueBack)throw QueueEmpty();
	return queue[queueBack];
}

template
void arrayQueue::pop()
{
	//删除队首元素
	if (queueFront == queueBack)throw QueueEmpty();
	queueFront = (queueFront + 1) % arrayLength;
	queue[queueFront].~T();
}
template
void arrayQueue::push(const T& theElement)
{
	//把元素theElement添加到队列的尾部
	//如果队列空间满，则加倍数组长度
	if (queueBack + 1) % arrayLength == queueFront){}//那就加倍数组长度。。一会写
	queueBack = (queueBack + 1) % arrayLength;
	queue[queueBack] = theElement;

}
//这是个节点
template
struct chainNode {
	//数据成员
	T element;
	chainNode* next;
	//多个构造函数重载
	chainNode() {}
	chainNode(const T& element)
	{
		this->element = element;
	}
	chainNode(const T& element, const chainNode* next)
	{
		this->element = element;
		this->next = next;
	}
};

//用链表实现
template
class linkedQueue :public queue
{
public:
	//构造函数
	linkedQueue(int initialCapacity = 10);
	~linkedQueue() {};

	bool empty()const { return queueSize == 0; }
	int size()const { return queueSize; }

	T& front();
	T& back();

	void push(const T& theElement);
	void pop();
private:
	chainNode* queueFront;//队列首指针
	chainNode* queueBack;//队列尾指针
	int queueSize;//队列中元素个数
};

template
linkedQueue::linkedQueue(int initCapacity)
{
	this->queueSize = initCapacity;
	this->queueFront = this->queueBack = new chainNode();
}

template
T& linkedQueue::front()
{
	//返回队列首元素
	if (queueSize == 0)throw QueueEmpty();
	return queueFront->element;
}

template 
T& linkedQueue::back()
{
	//返回队列尾元素
	if (queueSize == 0)throw QueueEmpty();
	return queueBack->element;
}
template 
void linkedQueue::push(const T& theElement)
{
	//把元素theElement加入到队尾
	//为新元素申请节点
	chainNode* newNode = new chainNode(theElement, NULL);
	//在队列尾部添加新节点
	if (queueSize != 0)
		queueBack->next = newNode;//队列不为空
	else queueFront = newNode;//队列为空
	queueBack = newNode;
	queueSize++;
}

template
linkedQueue& linkedQueue::pop()
{
	//删除队首元素
	if (queueFront == NULL)throw QueueEmpty();

	chainNode* nextNode = queueFront->next;
	delete queueFront;//删除第一个节点
	queueFront = nextNode;
	queueSize--;
}