データ構造スタックの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;
}