//順序棧類
#ifndef SEQSTACK_H
#define SEQSTACK_H
#include <assert.h>
#include <iostream>
using namespace std;
const int stackIncreament = 30; //棧溢出時(shí)擴(kuò)展空間的增量
template <class T>
class SeqStack{ //順序棧的類定義
public:
	SeqStack(int sz =50);					//建立一個(gè)空棧
	~SeqStack() {delete[]elements;}			//析構(gòu)函數(shù)
	void Push(const T& x);
	//如果IsFull()，則溢出處理；否則把x插入到棧的棧頂。
	bool Pop(T& x);
	//如果IsEmpty()，則不執(zhí)行退棧，返回false；否則退掉位于棧頂?shù)脑兀祷豻rue，
	//退出的元素值通過(guò)引用型參數(shù)x返回。
	bool getTop(T& x) const;
	//如果IsEmpty()，則返回false；否則返回true,并通過(guò)引用型參數(shù)x棧頂元素的值。
	bool IsEmpty()const {return (top == -1) ? true : false;}
	//如果棧中元素個(gè)數(shù)等于0，則返回true，否則返回false。
	bool IsFull()const {return (top == maxSize-1) ? true : false;}
	//如果棧中元素個(gè)數(shù)等于maxSize，則返回true，否則返回false。
	int getSize()const {return top+1;} //函數(shù)返回棧中元素個(gè)數(shù)。
	void MakeEmpty() {top = -1;} //清空棧的內(nèi)容
	friend ostream& operator << (ostream& os, SeqStack<T>& s)//輸出棧中元素的重載操作 <<
	{
		//輸出棧中元素的重載操作 <<
		os << "top = " << s.top << endl; //輸出棧頂位置
		for (int i = 0; i < s.top; i ++ ) //逐個(gè)輸出棧中元素的值
			os << i << " : " << s.elements[i] << endl;
		return os;
	}	
private:
	T *elements; //存放棧中元素的棧數(shù)組
	int top; //棧頂指針
	int maxSize; //棧最大可容納元素個(gè)數(shù)
	void overflowProcess(); //棧的溢出處理 
};

template <class T>
SeqStack<T>::SeqStack(int sz):top (-1), maxSize (sz) {
	//建立一個(gè)最大尺寸為sz的空棧, 若分配不成功則錯(cuò)誤處理。
	elements = new T[maxSize]; //創(chuàng)建棧的數(shù)組空間
	assert(elements != NULL); //斷言: 動(dòng)態(tài)存儲(chǔ)分配成功與否
};


template <class T>
void SeqStack<T>::overflowProcess() {
	//私有函數(shù)：擴(kuò)充棧的存儲(chǔ)空間。
	T *newArray = new T[maxSize + stackIncreament];
	if (newArray == NULL) {cerr << "存儲(chǔ)分配失敗！" << endl; exit(1);}
	for (int i = 0; i <= top; i++) newArray[i] = elements[i];
	maxSize = maxSize + stackIncreament;
	delete []elements;
	elements = newArray;
};


template <class T>
void SeqStack<T>::Push(const T& x) {
	//公共函數(shù)：若棧不滿, 則將元素x插入到該棧的棧頂, 否則溢出處理。
	if (IsFull()== true ) overflowProcess(); //棧滿則溢出處理
	elements[++top] = x; //棧頂指針先加1, 再進(jìn)棧
};


template <class T>
bool SeqStack<T>::Pop(T& x) {
	//公共函數(shù)：若棧不空則函數(shù)返回該棧棧頂元素的值, 然后棧頂指針退1。
	if (IsEmpty() == true) return false; //判棧空否, 若棧空則函數(shù)返回
	x = elements[top--]; //棧頂指針退1
	return true; //退棧成功
};


template <class T>
bool SeqStack<T>::getTop(T& x) const {
	//公共函數(shù)：若棧不空則函數(shù)返回該棧棧頂元素的地址。
	if (IsEmpty() == true) return false; //判棧空否, 若棧空則函數(shù)返回
	return elements[top]; //返回棧頂元素的值
	return true;
};
#endif;