순서 스 택 의 템 플 릿 클래스 구현

데이터 구조의 측면 에서 볼 때 스 택 도 선형 표 의 하나 로 그 특수성 은 스 택 의 기본 적 인 조작 이 선형 표 에 의 해 이 루어 진 것 이다.스 택 은 스 택 꼭대기 에서 만 삽입 과 삭제 작업 을 할 수 있 습 니 다.스 택 의 저장 방식 도 순서 스 택 과 체인 스 택 두 가지 로 나 뉘 는데 개인 적 으로 스 택 지붕 만 조작 하 는 이상 체인 스 택 은 의미 가 없다 고 생각 합 니 다.
#ifndef STACK_H_
#define STACK_H_
template <typename T>
class Stack
{
public:
    Stack(int size = Stack_init_size);
    //    
    ~Stack();
    Stack(const Stack<T> &s);
    //      
    const Stack<T>& operator=(const Stack<T> &s);
    //      
    void ClearStack();
    //   
    bool StackEmpty();
    //      TRUE    FALSE
    int StackLength();
    //      ,       
    bool GetTop(T &elem);
    //    , elem      ,   true,    ERROR
    void Push(T elem);
    //    elem       
    bool Pop(T &elem);
    //     ,       , elem    ,   true,    error

private:
    T *base;
    T *top;
    int m_size;
    enum StackSize
    {
        Stack_init_size = 100,          //         
        Stack_incerement = 10            //         
    };
};
template <typename T>
Stack<T>::Stack(int size)
{
    base = new T[Stack_init_size];
    if (base==NULL)
    {
        exit(1);
    }
    top = base;
    m_size = size;
}

template <typename T>
Stack<T>::Stack(const Stack<T> &s)
{
    base = new T[s.m_size];
    if (base == NULL)
    {
        exit(1);
    }
    top = base;
    m_size = s.m_size;
    T * p1 =s.base ;
    T * p2 = base;
    while (p1!=s.top)
    {
        *p2 = *p1;
        p1++;
        p2++;
    }
    top = p2;

}
template <typename T>
const Stack<T>& Stack<T>::operator=(const Stack<T> &s)
{
    delete[] base;
    base = new T[s.m_size];
    if (base == NULL)
    {
        exit(1);
    }
    top = base;
    m_size = s.m_size;
    T * p1 = s.base;
    T * p2 = base;
    while (p1 != s.top)
    {
        *p2 = *p1;
        p1++;
        p2++;
    }
    top = p2;
    return *this;
}

template <typename T>
Stack<T>::~Stack()
{
    delete[] base;
}


template <typename T>
int Stack<T>::StackLength()
{
    int n = 0;
    T * p = top;
    while (p!= base)
    {
        n++;
        p--;
    }
    return n;
}

template <typename T>
void Stack<T>::ClearStack()
{

    while (top != base)
    {
        top--;
        *top = 0;

    }

}
template <typename T>
bool Stack<T>::StackEmpty()
{
    if (top == base)
    {
        return true;
    }
    return false;
}
template <typename T>
bool Stack<T>::GetTop(T &elem)
{
    if (StackEmpty())
    {
        return false;
    }
    else
    {

        top--;
        elem = *top;
        *top = 0;
        return true;
    }

}
template <typename T>
void Stack<T>::Push(T elem)
{
    int size_increment;
    if (top - base>Stack_init_size)
    {
        m_size = m_size + Stack_incerement;
        T *temp = new T[m_size];
        T *p = base;
        T *q = temp;
        while ((p + 1) != top)
        {
            *q = *p;
            q++;
            p++;
        }
        delete[] base;
        base = temp;
        *q = elem;
        q++;
    }
    else
    {
        *top = elem;
        top++;
    }

}

template <typename T>
bool Stack<T>::Pop(T &elem)
{
    if (top == base)
    {
        return false;
    }
    top--;
    elem = *top;
    *top = 0;
    return true;
}

#endif

template macro auto 등 은 모두 헤더 파일 에서 볼 수 있어 야 하 며, 성명 과 정 의 를 독립 적 으로 컴 파일 할 수 없습니다.

좋은 웹페이지 즐겨찾기