栈

/*
 * 栈测试代码
 arrayStack.cpp
*/
#include<iostream>
#include"arraystack.h"
#include"myexceptions.h"

using namespace std;
int main(void)
{
    arrayStack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);

    cout <<"Stack should be 1234,bottom to top"<<endl;

    if(s.empty())
        cout<<"The stack is empty"<<endl;
    else
        cout <<"The stack is not empty"<<endl;

    cout <<"The stack size is "<<s.size()<<endl;

    while(!s.empty())
    {
        cout <<"Stack top is "<<s.top()<<endl;
        s.pop();
        cout<<"Popped top element"<<endl;
    }

    try{s.pop();}
    catch(stackEmpty message)
    {
        cout <<"Last pop failed"<<endl;
        message.outputMessage();
    }

    return 0;
}

/*栈操作的头文件
 * 规定了栈操作的可能使用函数
 * stack.h
*/
#ifndef STACK_H
#define STACK_H

using namespace std;

template<class T>
class stack
{
public:
    virtual ~stack(){}

    //判断是否空栈
    virtual bool empty()const = 0;

    //返回栈空间中元素数量
    virtual int size() const = 0;

    //返回栈顶元素的索引
    virtual T& top() = 0;

    //出栈操作
    virtual void pop() = 0;

    //入栈操作
    virtual void push(const T& theElement) = 0;
};


#endif // STACK_H

/*
 * 对抽象类stack的具体实现
 * arrayStack.h
*/

#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H

#include"stack.h"
#include"myexceptions.h"
#include"changelength1d.h"
#include<sstream>

template<class T>
class arrayStack : public stack<T>
{
  public:
    arrayStack(int initialCapacity = 10);
    ~arrayStack(){delete [] stack;}

    bool empty() const{return stackTop == -1;}
    int size() const
    {
        return stackTop + 1;
    }
    T& top()
    {
        if(stackTop == -1)
            throw stackEmpty();
        return stack[stackTop];
    }
    void pop()
    {
        if(stackTop == -1)
            throw stackEmpty();
        stack[stackTop--].~T();
    }
    void push(const T &theElement);
private:
    int stackTop;
    int arrayLength;
    T *stack;
};

template<class T>
arrayStack<T>::arrayStack(int initialCapacity)
{
    if(initialCapacity < 1)
    {
        ostringstream s;
        s <<"Initial capacity = "<<initialCapacity
         <<"Must be > 0";
        throw illegalParameterValue(s.str());
    }
    arrayLength = initialCapacity;
    stack = new T[arrayLength];
    stackTop = -1;
}

template<class T>
void arrayStack<T>::push(const T &theElement)
{
    if(stackTop == arrayLength - 1)
    {
        changeLength1D(stack,arrayLength,arrayLength*2);
        arrayLength *= 2;
    }
    stack[++stackTop] = theElement;
}


#endif // ARRAYSTACK_H

/*
 * 变长数组：1维
 * changeLength1D.h
*/
#ifndef CHANGELENGTH1D_H
#define CHANGELENGTH1D_H

#include"myexceptions.h"

using namespace std;

int min(int a,int b)
{
    return (a >= b)?b:a;
}

template<class T>
void changeLength1D(T*& a,int oldLength,int newLength)
{
    if(newLength < 0)
        throw illegalParameterValue("new length must be >= 0");

    T* temp = new T[newLength];
    int number = min(oldLength,newLength);
    copy(a,a+number,temp);
    delete [] a;
    a = temp;
}

#endif // CHANGELENGTH1D_H

/*
 * 栈操作的异常处理类
 * myExceptions.h
*/
#ifndef MYEXCEPTIONS_H
#define MYEXCEPTIONS_H

#include<string>

using namespace std;


//参数不合法异常
class illegalParameterValue
{
public:
    illegalParameterValue(string theMessage =
            "Illegal parameter value")
    {
        message = theMessage;
       // 10.95.251.52
    }
    void outputMessage()
    {
        cout <<message<<endl;
    }
private:
    string message;
};


//栈空异常
class stackEmpty
{
public:
    stackEmpty(string theMessage =
            "Invalid operation on empty stack")
    {
        message = theMessage;
    }
    void outputMessage()
    {
        cout <<message <<endl;
    }
private:
    string message;
};

#endif // MYEXCEPTIONS_H