#ifndef SEQSTACK_H
#define SEQSTACK_H
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <assert.h>
#include "Stack.h"
const int stackIncreament = 20;				//栈溢出时扩展空间的增量
template<class T>
class SeqStack : public Stack<T>			//顺序栈
{
public:
	SeqStack(int sz = 50);
	~SeqStack(){ delete[] elements;}
	void Push(const T& x);					//如果IsFull()，则溢出处理，否则把x插入到栈的顶部
	bool Pop(T& x);							//如果IsEmpty(),则不执行退栈，返回false，否则退掉位于栈顶的元素，返回true，退出的元素值通过x返回
	bool getTop(T& x);						//如果IsEmpty(),则返回false，否则返回true，并通过引用类型x得到得到栈顶元素的值。
	bool IsEmpty()const
	{
		return (top == -1)?true:false;
	}
	bool IsFull()const
	{
		return (top == maxSize - 1)?true:false;
	}
	int getSize()
	{
		return top+1;
	}
	void makeEmpty()
	{
		top = -1;
	}
	friend ostream& operator << (ostream& os, SeqStack<T>& s);
private:
	T * elements;
	int top;
	int maxSize;
	void overflowProcess();					//栈溢出处理
};
template<class T>
SeqStack<T>::SeqStack(int sz  ):top(-1),maxSize(sz)
{
	elements = new T[maxSize];
	assert(elements != NULL);
}
template<class T>
void SeqStack<T>::overflowProcess()
{//私有函数，扩充栈的存储空间
	T * newArray = new T[maxSize + stackIncreament];
	if(newArray == NULL)
	{
		cerr<< "存储分配失败!" << 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)
{//若栈不满，插入元素x到栈顶
	if(IsFull() == true)
		overflowProcess();
	elements[++top] = x;
}
template<class T>
bool SeqStack<T>::Pop(T& x)
{//若栈不空，则返回该栈栈顶元素的值，栈顶指针退1
	if(IsEmpty() == true)
		return false;
	x = elements[top--];
	return true;
}
template<class T>
bool SeqStack<T>::getTop(T& x)
{//若栈不空，函数返回该栈栈顶元素的值
	if(IsEmpty() == true) 
		return false;
	x = elements[top];
	return true;
}
template<class T>
ostream& operator << (ostream& os,SeqStack<T> s)
{//输出栈中元素的重载操作
	os<<"top = "<<s.top<<endl;
	for(int i =0; i< s.top;i++)
		os<< i <<":"<<s.elements[i]<<endl;
	return os;
}
#endif