//程序名：Stack.h
//程序功能：棧類的頭文件
//作者：黃秋旋
//日期：2008.12.20
//版本：1.0
//修改內容：
//修改日期：
//修改作者：
//對應類實現文件: labyrinth.h
//對應主程序文件: labyrinth.cpp



#include<iostream.h>
#include<stdlib.h>

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


struct items         //存儲通路坐標信息的結構體
{
	int x,y,d;
};

typedef items Type;


struct Node         //棧節點的結構體
{
	Type data; 
	Node *next;
};

class Stack      //棧類定義
{
private:
	Node *atop;

public:
	Stack(){atop=NULL;};  //構造函數
	~Stack();   //析構函數
	Type top();  //取棧頂函數
	void pop();  //出棧函數
	bool empty();  //判空函數
	bool push(Type& x);  //壓棧函數
};


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：析構函數
//函數功能：釋放棧類的空間
//函數參數：無
//參數返回值：無

Stack::~Stack()
{
	Node *p;
	while(atop!=NULL)
	{
		p=atop;
		atop=atop->next;
		delete p;  //釋放節點p的空間
	}//while
};


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：取棧頂元素
//函數功能：取出棧頂元素
//函數參數：無
//參數返回值：atop->data ：棧頂元素的數據

Type Stack::top()
{
	if(atop==NULL)
		exit(1);
	else
		return (atop->data);     //返回棧頂元素的內容
};


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：出棧函數
//函數功能：使棧頂元素出棧
//函數參數：無
//參數返回值：無

void Stack::pop()
{
	if(atop==NULL) exit(1);  //當棧為空時，正常退出
	else 
	{
	    atop=atop->next;  //棧頂指針指向下一個元素
	}
};


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：判空函數
//函數功能：判斷棧是否為空
//函數參數：無
//參數返回值：bool：當棧為空時返回，否則返回0

bool Stack::empty()
{
	return atop==NULL;
};


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：壓棧函數
//函數功能：將通路數據壓入棧中
//函數參數：Type &x:表示按引用方式，將通路的實參傳給函數
//參數返回值：bool：壓棧完成時返回true

bool Stack::push(Type &x)
{
	Node *p;
	p=new Node;  //為節點指針p申請空間
	p->data=x;  //將通路信息賦給p的數據域
	p->next=atop;  //用頭插入的方式將節點p插入到棧鏈中
	atop=p;  //棧頂指針指向p
    return true;  //壓棧完成，返回true
};