//LinkQueue.cpp
#include "LinkQueue.h"

/*
 * 前置條件：隊列不存在
 * 輸    入：無
 * 功    能：初始化隊列
 * 輸    出：無
 * 后置條件：創建一個空隊列
 */

template <class T>
LinkQueue<T>::LinkQueue( )
{
	Node <T> *s;
	s=new Node<T>;
	s->next=NULL;
	front=rear=s;
}

/*
 * 前置條件：隊列存在
 * 輸    入：無
 * 功    能：銷毀隊列
 * 輸    出：無
 * 后置條件：釋放隊列所占用的存儲空間
 */

template <class T>
LinkQueue<T>::~LinkQueue( )
{
	while(front)
	{
		Node <T> *p;
		p=front->next;
        delete front;
	    front=p;
	}
}

/*
 * 前置條件：隊列已存在
 * 輸    入：元素值s
 * 功    能：在隊尾插入一個元素
 * 輸    出：無
 * 后置條件：如果插入成功，隊尾增加了一個元素
 */

template <class T> 
void LinkQueue<T>::EnQueue(T x)
{
	Node<T> *s;
    s=new Node<T>; 
    s->data=x;          //申請一個數據域為x的結點s
    s->next=NULL;
    rear->next=s;       //將結點s插入到隊尾
    rear=s;
}

/*
 * 前置條件：隊列已存在
 * 輸    入：無
 * 功    能：刪除隊頭元素
 * 輸    出：如果刪除成功，返回被刪元素值，否則，拋出刪除異常
 * 后置條件：如果刪除成功，隊頭減少了一個元素
 */

template <class T>
T LinkQueue<T>::DeQueue()
{    
	Node <T> *p; int x;
    if (rear==front) throw "下溢";
    p=front->next; 
	x=p->data;                       //暫存隊頭元素
    front->next=p->next;             //將隊頭元素所在結點摘鏈
    if (p->next==NULL) rear=front;   //判斷出隊前隊列長度是否為1
    delete p;
    return x;
}

/*
 * 前置條件：隊列已存在
 * 輸    入：無
 * 功    能：讀取隊頭元素
 * 輸    出：若隊列不空，返回隊頭元素
 * 后置條件：隊列不變
 */

template <class T> 
T LinkQueue<T>::GetQueue()
{
    if (front!=rear) 
		return front->next->data;
}

/*
 * 前置條件：隊列已存在
 * 輸    入：無
 * 功    能：判斷隊列是否為空
 * 輸    出：如果隊列為空，返回1，否則，返回0
 * 后置條件：隊列不變
 */

template <class T> 
bool LinkQueue<T>::Empty( )
{
    if(front==rear) 
		return 1;
    else 
		return 0;
}