数据结构-队列

template<typename T>
class Node {
public:
	Node() {}
	Node(T data, Node<T> *nextptr) :data(data), next(nextptr) {
	}
	~Node() {}
	T ();
	void setData(T newData);
	Node<T> *getNext();
	void setNext(Node<T> *ptr);
private:
	T data;
	Node<T> *next;
};
template<typename T>
T Node<T>::getData() {
	return data;
}
template<typename T>
void Node<T>::setData(T newData) {
	data = newData;
}
template<typename T>
Node<T> *Node<T>::getNext() {
	return next;
}
template<typename T>
void Node<T>::setNext(Node<T> *ptr) {
	next = ptr;
}

#include<iostream>
template<typename T>
class LinkQueue {
public:
	LinkQueue();
	LinkQueue(T array[], int n);
	~LinkQueue();
	void EnQueue(T x);
	T DeQueue();
	T GetQueue();
	bool QueueEmpty();
private:
	Node<T> *front;	
	Node<T> *rear;	//队尾指针，指向终端节点
};
template<typename T>
LinkQueue<T>::LinkQueue() {
	Node<T> *s = new Node<T>;
	s->setNext(NULL);
	front = s;
	rear = s;
}
template<typename T>
LinkQueue<T>::LinkQueue(T array[], int n) {
	Node<T> *s;
	front = new Node<T>;
	rear = front;
	rear->setNext(NULL);
	for (int i = 0; i < n; i++) {
		s = new Node<T>;
		s->setData(array[i]);
		s->setNext(NULL);
		rear->setNext(s);
		rear = s;
	}
	
}
template<typename T>
LinkQueue<T>::~LinkQueue() {
	Node<T> *p = front;
	Node<T> *q = p->getNext();
	while (q != NULL) {
		delete p;
		p = q;
		q = q->getNext();
	}
	delete p;	//删除最后一个节点
}
template<typename T>
void LinkQueue<T>::EnQueue(T x) {
	Node<T> *s = new Node<T>;
	s->setData(x);
	s->setNext(NULL);
	rear->setNext(s);
	rear = s;
}
template<typename T>
T LinkQueue<T>::DeQueue() {
	Node<T> *s;
	if (rear == front) {
		throw "链表为空！";
	}
	else {
		s = front->getNext();
		T x = s->getData();
		front->setNext(s->getNext());
		if (s->getNext() == NULL) {
			rear = front;
		}
		delete s;
		return x;
	}
}
template<typename T>
T LinkQueue<T>::GetQueue() {
	if (rear == front) {
		throw "链表为空！";
	}
	else {
		return front->getNext()->getData();
	}
}
template<typename T>
bool LinkQueue<T>::QueueEmpty() {
	if (front == rear) {
		return true;
	}
	else {
		return false;
	}
}

const int QueueSize = 5;
template<typename T>
class CirQueue {
public:
	CirQueue();
	~CirQueue() {};
	void EnQueue(T x);
	T DeQueue();
	T GetQueue();
private:
	T data[QueueSize];
	int front, rear;
};
template<typename T>
CirQueue<T>::CirQueue() {
	rear = front = QueueSize - 1;
}
template<typename T>
void CirQueue<T>::EnQueue(T x) {
	if ((rear + 1) % QueueSize == front) {
		throw "队列已满！";
	}
	else {
		rear = (rear + 1) % QueueSize;
		data[rear] = x;
	}
}
template<typename T>
T CirQueue<T>::DeQueue() {
	if (rear == front) {
		throw "队列已空！";
	}
	else {
		front = (front + 1) % QueueSize;
		return data[front];
	}
}
template<typename T>
T CirQueue<T>::GetQueue() {
	if (rear == front) {
		throw "队列已空！";
	}
	else {
		int i = (front + 1) % QueueSize;
		return data[i];
	}
}