データ構造スタックのC++実装
2681 ワード
#include <iostream>
#include <stdexcept>
#include <malloc.h>
using namespace std;
namespace my_space
{
template<class ElemType>
class stack
{
public:
stack(); //
~stack(); //
void clear(); //
bool empty() const;//
int length() const;//
ElemType gettop() throw(out_of_range);//
void push(ElemType e); // e
ElemType pop() throw(out_of_range); //
private:
class st
{
public:
ElemType *base;
ElemType *top;
int stacksize;
int length;
};
st sqstack;
static const int stack_init_size = 100; //
static const int stackincrement = 10; //
};
template<class ElemType>
stack<ElemType>::stack()
{
sqstack.base = new ElemType[stack::stack_init_size];
sqstack.top = sqstack.base;
sqstack.stacksize = stack::stack_init_size;
sqstack.length = 0;
}
template<class ElemType>
stack<ElemType>::~stack()
{
delete [] sqstack.base;
sqstack.length = 0;
sqstack.stacksize = 0;
}
template<class ElemType>
void stack<ElemType>::clear()
{
sqstack.top = sqstack.base;
sqstack.length = 0;
}
template<class ElemType>
bool stack<ElemType>::empty() const
{
return sqstack.length == 0;
}
template<class ElemType>
int stack<ElemType>::length() const
{
return sqstack.length;
}
template<class ElemType>
ElemType stack<ElemType>::gettop() throw(out_of_range)
{
if(sqstack.top == sqstack.base)
throw("stack is empty!");
return *(sqstack.top - 1);
}
template<class ElemType>
void stack<ElemType>::push(ElemType e)
{
if(sqstack.top - sqstack.base >= sqstack.stacksize)
{
sqstack.base = (ElemType*)realloc(sqstack.base, (sqstack.stacksize + stack::stackincrement)*sizeof(ElemType));
sqstack.top = sqstack.base + sqstack.stacksize;
sqstack.stacksize += stack::stackincrement;
}
*sqstack.top++ = e;
++sqstack.length;
}
template<class ElemType>
ElemType stack<ElemType>::pop() throw(out_of_range)
{
if(sqstack.base == sqstack.top)
throw("stack is empty");
--sqstack.length;
return *--sqstack.top;
}
}
int main()
{
return 0;
}