#ifndef __NODE_H__
#define __NODE_H__

// 结点类模板
template <class ElemType>
struct Node 
{
// 数据成员:
    ElemType data;            // 数据域
    Node<ElemType> *next;        // 指针域
};
#endif

#ifndef __LINK_STACK_H__
#define __LINK_STACK_H__
#include "node.h"
#include <iostream>
using namespace std;
template<class ElemType>
class LinkStack 
{
    private:
        Node<ElemType> *top;    // 栈顶指针
        int count;     //栈长度
    public:
        LinkStack( );  
        virtual ~LinkStack( );
        void  Clear( );
         bool  Empty( );
        int  Length( );
        bool Push(ElemType e); //新元素入栈
        bool Pop(ElemType &e); //出栈，即删除栈顶元素
        bool Top(ElemType &e); //读栈，即读取栈顶元素
        void Traverse( );
        //void SysConvert();
};

template<class ElemType>
LinkStack<ElemType>::LinkStack(){
    top = NULL;
    count=0;
    return;
}


template <class ElemType>
LinkStack<ElemType>:: ~LinkStack( ){
    Clear();    
}


template<class ElemType>
void LinkStack<ElemType>::Clear(){
    Node<ElemType> *p;
    while(top!=NULL){        
        p=top;
        top=top->next;
        delete p;
    }
    count=0;
}

template<class ElemType>
bool LinkStack<ElemType>::Empty(){
    return top == NULL;
}


template <class ElemType>
int LinkStack<ElemType>::Length(){
    return count;
}


template<class ElemType>
bool LinkStack<ElemType>::Push(ElemType e){    
    Node<ElemType> *newtop = new Node<ElemType>;
    newtop->data =http://www.mamicode.com/ e;
    newtop->next = top;
    top = newtop;    
    count++;
    return true;

}


template<class ElemType>
bool LinkStack<ElemType>::Pop(ElemType &e) {
    if (Empty()){
        return false;
    }else{
        Node<ElemType> *old_top = top;    
        e = old_top->data;                
        top = old_top->next;            
        delete old_top;    count--;                
        return true;
    }
}


template<class ElemType>
bool LinkStack<ElemType>::Top(ElemType &e){
    if(Empty()){
        return false;
    }else{
        e = top->data;    
        return true;
    }
}


template <class ElemType>
void LinkStack<ElemType>::Traverse( ) {  
    Node<ElemType> *tmpPtr;        
    for (tmpPtr = top; tmpPtr != NULL; tmpPtr = tmpPtr->next){
        cout<<tmpPtr->data<<‘\t‘;    
    }
}



















#endif

#ifndef __SQ_STACK_H__
#define __SQ_STACK_H__

#include "node.h"
#include <iostream>
using namespace std;

template <class ElemType>
class SqStack{
    private:
        int count;
        int maxSize;
        ElemType *elems;
    public:
        SqStack( int  size);  //size为栈的长度
        virtual ~SqStack( );
        void  Clear( );
        bool  Empty( );
        int  Length( );
        bool Full();
        bool Push(ElemType e); //新元素入栈
        bool Pop(ElemType &e); //出栈，即删除栈顶元素
        bool Top(ElemType &e); //读栈，即读取栈顶元素
        void Traverse( );

};


template <class ElemType>
SqStack<ElemType>::SqStack(int size){
    elems = new ElemType[maxSize];
    if(elems == NULL){
        cout << "init error.";
        return;
    }
    maxSize = size;
    count = 0;
    return;
}


template <class ElemType>
SqStack<ElemType>::~SqStack(){
    delete []elems;
    maxSize = 0;
    count = 0;
    return;
} 


 template <class ElemType>
 void SqStack<ElemType>::Clear(){
     count = 0;
     return;
 }


template <class ElemType>
bool SqStack<ElemType>::Empty(){
    
    return count == 0;
}

template <class ElemType>
bool SqStack<ElemType>::Full(){
    return count == maxSize;
}

template <class ElemType>
int SqStack<ElemType>::Length(){
    return count;
}


template <class ElemType>
bool SqStack<ElemType>::Push(ElemType e){
    if(Full()){
        cout << "fulled";
        return false;
    }else{
        elems[count] = e;
        ++count;
        return true;
    }
    return false;
}


template <class ElemType>
bool SqStack<ElemType>::Pop(ElemType &e){
    if(Empty()){
        return false;
    }else{
        e = elems[count - 1];
        --count;
        return true;
    }
    return false;
}

template <class ElemType>
bool SqStack<ElemType>::Top(ElemType &e){
    if(Empty()){
        cout << "Empty";
        return false;
    }else{
        e = elems[count-1];
        
    }
    return true;
}

template <class ElemType>
void SqStack<ElemType>::Traverse(){
    for(int i = 1; i <= count; ++i){
        cout << elems[i-1];
    }
    return;
}
#endif

#include "lk_stack.h"        // 

#include "sq_stack.h"    
#define ElemType int
#define DEFAULT_SIZE 3
//#include <iostream>
//using namespace std;
int main(void){
    LinkStack<ElemType> l;
    SqStack<ElemType> s(DEFAULT_SIZE);
    int c = 0;
    while(c != 100){
        cout << "\n1. 链式栈入栈.";
        cout << "\n2. 链式栈遍历.";
        cout << "\n3. 链式栈出栈.";
        cout << "\n4. 链式栈读栈.";
        cout << "\n5. 链式栈清空.";
        cout << "\n6. 链式栈销毁.";
        cout << "\n7. 顺序栈入栈.";
        cout << "\n8. 顺序栈出栈.";
        cout << "\n9. 顺序栈销毁.";
        cout << "\n10. 顺序栈清空.";
        cout << "\n11. 顺序栈读栈."; 
        cout << "\n12. 顺序栈判断是否为空.";
        cout << "\n13. 顺序栈求长.";
        cout << "\n14. 顺序栈遍历.";
        cout << "\n15. SysConvert.";//进制转换，基于LinkStack.h 
        cout << "\n16. .";
        cout << "\n17. .";
        cin >> c;
        switch(c){
            case 1:
                ElemType i;
                cout << "input element: ";
                cin >> i;
                l.Push(i);
                break;
            case 2:
                l.Traverse();
                break;
            case 3:
                ElemType j;
                l.Pop(j);
                break;
            case 4:
                ElemType e;
                l.Top(e);
                break;
            case 5:
                l.Clear();
                break;
            case 6:
                l.~LinkStack();
                break;
            case 9:
                s.~SqStack();
                break;
            case 10:
                s.Clear();
                break;
            case 12:
                if(s.Empty()){
                    cout << "is emp";
                }else{
                    cout << "not emp";
                }
                break; 
            case 13:
                cout << s.Length(); 
                break;
            case 7:
                ElemType p;
                cout << "input element:";
                cin >> p;
                s.Push(p);
                break;
            case 8:
                ElemType pop;
                s.Pop(pop);
                cout << "poped " << pop;
                break;
            case 11:
                ElemType top;
                s.Top(top);
                break;
            case 14:
                s.Traverse();
                break;
            case 15:
                break;
            case 16:
                break;
        }
    }
    return 0;
}