链栈 原

	//测试函数
	//linkedStack.h
#include<iostream>
#include"linkedstack.h"
#include"myexceptions.h"

using namespace std;
int main(int argc, char *argv[])
{
    linkedStack<int> s;

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

    cout<<"Stack shoule 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;
}

/*
 * 链栈类
 * linkedStack.h
*/
#ifndef LINKEDSTACK_H
#define LINKEDSTACK_H

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

using namespace std;

template<class T>
class linkedStack : public stack<T>
{
public:
    linkedStack(int initialCapacity = 10)
    {
        stackTop = NULL;
        stackSize = 0;
    }
    ~linkedStack();
    bool empty() const
    {
        return stackSize == 0;
    }

    int size() const
    {
        return stackSize;
    }

    T& top()
    {
        if(stackSize == 0)
            throw stackEmpty();
        return stackTop->element;
    }

    void pop();
    void push(const T &theElement)
    {
        stackTop = new chainNode<T>(theElement,stackTop);
                stackSize++;
    }

private:
    chainNode<T>* stackTop;//栈顶指针
    int stackSize;//栈中所含元素个数
};

template<class T>
linkedStack<T>::~linkedStack()
{
    while(stackTop != NULL)
    {
        chainNode<T>* nextNode = stackTop->next;
        delete stackTop;
        stackTop = nextNode;
    }
}

template<class T>
void linkedStack<T>::pop()
{
    if(stackSize == 0)
    {
        throw stackEmpty();
    }

    chainNode<T>* nextNode = stackTop->next;
    delete stackTop;
    stackTop = nextNode;
    stackSize--;
}
#endif

/*
 * 栈类的定义
 * 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

/*
 * 链表节点类
 * chainNode.h
*/
#ifndef CHAINNODE_H
#define CHAINNODE_H
template<class T>
struct chainNode
{
  T element;
  chainNode<T> *next;

  chainNode(){}
  chainNode(const T& element)
  {
      this->element = element;
  }
  chainNode(const T &element,chainNode<T>* next)
  {
      this->element = element;
      this->next = next;
  }
};

#endif // CHAINNODE_H

/*
 * 异常类
 * myExceptions.h
*/
#ifndef MYEXCEPTIONS_H
#define MYEXCEPTIONS_H
#include<string>

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

//

#endif // MYEXCEPTIONS_H