#ifndef LINKEDQUEUE_H
#define LINKEDQUEUE_H
#include <iostream>
#include "LinkedList.h"
template <class T>
class LinkedQueue { //鏈式隊列類定義
public:
	LinkedQueue() : rear(NULL),front(NULL) {} //構造函數, 建立空隊列
	bool EnQueue(const T& x); //將x加入到隊列中
	bool DeQueue(T& x); //刪除隊頭元素,x返回其值
	bool getFront(T& x)const; //查看隊頭元素的值
	void makeEmpty(); //置空隊列
	bool IsEmpty()const {return (front == NULL) ? true : false;}
	//判隊列空否
	int getSize()const; //求隊列元素個數
	void show();//輸出
protected:
	LinkNode<T,T> *front, *rear; //隊頭、隊尾指針
};
template <class T>
void LinkedQueue<T>::makeEmpty() {
	//置空隊列，釋放鏈表中所有結點。
	LinkNode<T,T> *p;
	while (front != NULL) { //逐個刪除隊列中的結點
		p = front; front = front->link; delete p;
	}
};
template <class T>
bool LinkedQueue<T>::EnQueue(const T& x) {
	//將新元素x插入到隊列的隊尾(鏈式隊列的鏈尾)。
	if (front == NULL)
	{
		front = rear = new LinkNode<T,T>(x);
	//空隊列時，新結點成為隊列的第一個結點，既是隊頭又是隊尾
	if (front == NULL) return false; //分配結點失敗
	}
	else {
		rear->link = new LinkNode<T,T>(x);
		//非空隊列時，在鏈尾追加新的結點并更新隊尾指針
		if (rear->link == NULL) return false; //分配結點失敗
		rear = rear->link;
	}
	return true;
};
template <class T>
bool LinkedQueue<T>::DeQueue(T& x) {
	//如果隊列不為空，將隊頭結點從鏈式隊列中刪去，函數返回true，否則返回false。
	if (IsEmpty() == true) return false; //隊列空則返回false
	LinkNode<T,T> *p = front; //隊列不空，暫存隊頭結點
	x = front->data;
	front = front->link; delete p; //隊頭修改，釋放原隊頭結點 124
	return true; //函數返回true
};
template <class T>
bool LinkedQueue<T>::getFront(T& x)const {
	//若隊列不空，則函數返回隊頭元素的值及true。若隊列空，則函數返回false。
	if (IsEmpty() == true) return false; //隊列空則返回false
	x = front->data; //取隊頭元素中的數據值
	return true;
};
template <class T>
int LinkedQueue<T>::getSize()const {
	//求隊列元素個數。
	LinkNode<T,T> *p = front; int k = 0;
	while (p != NULL) {p = p->link; k++;}
	return k;
};
template <class T>
void LinkedQueue<T>::show() {
	//輸出隊列中元素
	cout << "隊列中元素個數有"<< getSize() << endl;
	LinkNode<T,T> *p = front; int i = 1;
	while (i<=getSize())
	{
		cout << i << " : " << p->data << endl;
		p = p->link;
        i++;
	}
};
#endif;