˳ÐòÕ»

1¡¢C++°æµÄ˳ÐòÕ»

/***********************/
/*****  seqStack.h  ****/
/***********************/

#ifndef _SEQSTACK_H
#define _SEQSTACK_H

template <class T>
class SeqStack
{
    public:
        SeqStack(int capacity = 15);
        ~SeqStack();

        void ChangeCapacity(T* &st, int oldCapacity, int newCapacity);
        bool IsEmpty() const;
        T& Top() const;
        void Push(const T& item);
        T Pop();

    private:
        T *stack;
        int capacity;
        int top;
};

template <class T>
SeqStack<T>::SeqStack(int stackCapacity):capacity(stackCapacity)
{
    if (capacity < 1)
        throw "Stack capacity must be > 0";
    stack = new T[capacity];
    top = -1;
}

template <class T>
SeqStack<T>::~SeqStack()
{
    delete[] stack;
}

template <class T>
void SeqStack<T>::ChangeCapacity(T* &st, int oldCapacity, int newCapacity)
{
    if (newCapacity < 0)
        throw "Realloc storge cannot < 0";

    T *temp = new T[newCapacity];

    int number = std::min(oldCapacity, newCapacity);
    std::copy(st, st + number, temp);

    delete[] st;
    st = temp;
    capacity = newCapacity;
}

template <class T>
bool SeqStack<T>::IsEmpty() const
{
    return (top == -1);
}

template <class T>
inline T& SeqStack<T>::Top() const
{
    if (IsEmpty())
        throw "Stack is empty!";
    return stack[top];
}

template <class T>
void SeqStack<T>::Push(const T& item)
{
    if (top == capacity-1){
        ChangeCapacity(stack, capacity, 2*capacity);
    }

    stack[++top] = item;
}

template <class T>
T SeqStack<T>::Pop()
{
    if (IsEmpty())
        throw "Stack is empty!";
    return stack[top--];
}

#endif

/***********************/
/*****   main.cpp   ****/
/***********************/

#include <iostream>
#include "seqStack.h"

using namespace std;

int main(int argc, const char *argv[])
{
    SeqStack<int> st;

    int i;

    if (st.IsEmpty())
        cout << "Stack is empty!" << endl;

    cout << "Push data in..." << endl;
    for (i = 0; i < 30; i++){
        st.Push(i);
        cout << st.Top() << "  ";
    }
    cout << endl;

    cout << "Top of stack" << endl;
    cout << st.Top() << endl;

    cout << "Pop data out..." << endl;
    for (i = 0; i < 30; i++)
        cout << st.Pop() << "  ";
    cout << endl;

    return 0;
}