template <class T> class LinStack;			//前視定義,否則友元無法定義

template <class T>							//模板類型為T
class StackNode
{
	friend class LinStack<T>;				//定義類LinStack<T>為友元
private:
	T data;									//數據元素
	StackNode<T> *next;	    				//指針
public:
	//構造函數1,用于構造頭結點
	StackNode(StackNode<T> *ptrNext = NULL)
		{next = ptrNext;}
	
	//構造函數2,用于構造其他結點
	StackNode(const T& item, StackNode<T> *ptrNext = NULL)
		{data = item;	next = ptrNext;}

	~StackNode(){};
};

template <class T>
class LinStack
{
private:
	StackNode<T> *head;				//頭指針
	int size;						//數據元素個數
public:
	LinStack(void);					//構造函數
	~LinStack(void);				//析構函數

	void Push(const T& item);		//入棧
	T Pop(void);					//出棧
	T GetTop(void)const;			//取棧頂元素
	int NotEmpty(void) const;		//堆棧非空否
};
 
//堆棧類的實現  
template <class T> 
LinStack<T>::LinStack()				//構造函數
{
	head = new StackNode<T>;		//頭指針指向頭結點
	size = 0;						//size的初值為0
}

template <class T>
LinStack<T>::~LinStack(void)		//析構函數
//釋放所有動態申請的結點空間
{ 
	StackNode<T> *p, *q;

	p = head;						//p指向頭結點
	while(p != NULL)				//循環釋放結點空間
	{
       	q = p;
		p = p->next;
		delete q;
	}
}

template <class T>
int LinStack<T>::NotEmpty(void) const	//堆棧非空否
{
	if(size != 0) return 1;
	else return 0;
}
	
template <class T>
void LinStack<T>::Push(const T& item)			//入棧
{
	//新結點newNode的data域值為item，next域值為 head->next
	StackNode<T> *newNode = new StackNode<T>(item, head->next);

	head->next = newNode;						//新結點插入棧頂
	size++;										//元素個數加1
}

template <class T>
T LinStack<T>::Pop(void)						//出棧
{
	if(size == 0) 
	{
		cout << "堆棧已空無元素可刪！" << endl;
		exit(0);
	}
		
	StackNode<T> *p = head->next;	//p指向棧頂元素結點
	T data = p->data;				
	head->next = head->next->next;	//原棧頂元素結點脫鏈
	delete p;						//釋放原棧頂結點空間
	size--;							//結點個數減1
	return data;					//返回原棧頂結點的data域值
}

template <class T>
T LinStack<T>::GetTop(void)const			//取棧頂元素
{
	return head->next->data;
}