栈的实现 -- 顺序栈和链式栈（C++描述）

喜欢ヅ旅行 2022-08-22 13:25 201阅读 0赞

## 栈的ADT C++描述： ##

#ifndef STACKADT_H
    #define STACKADT_H
    
    template <typename E>
    class Stack{
    private:
        void operator =(const Stack&){}
        Stack(const Stack&){}
    public:
        Stack(){}
        virtual ~Stack(){}
    
        //重置栈。删除所有元素，回收空间。
        virtual void clear() = 0;
    
        //入栈
        virtual void push(const E& it) = 0;
    
        //出栈并返回栈顶元素
        virtual E pop() = 0;
    
        //栈顶元素的copy
        virtual const E& topValue() const = 0;
    
        //栈中元素个数
        virtual int length() const = 0;
    };
    #endif

--------------------

## 链表头结点定义： ##

#ifndef LINKNODE_H
    #define LINKNODE_H
    //单链表结点定义
    template <typename E>
    class Link{
    public:
        E element;                          //节点的值
        Link* next;                         //next
        Link(const E& elemval, Link* nextval = NULL){
            element = elemval;
            next = nextval;
        }
        Link(Link* nextval = NULL){
            next = nextval;
        }
    };
    #endif

--------------------

## 顺序栈的实现： ##

template <typename E>
    class AStack : public Stack{
    private:
        int maxSize;
        int top;
        E* listArray;
    
    public:
        AStack(int size = defaultSize){
            maxSize = size;
            top = 0;
            listArray = new E[size];
        }
    
        ~AStack(){
            delete[] listArray;
         };
    
    
        void clear(){
            top = 0;
        }
    
        void push(const E& it){
            Assert(top != 0, "Stack is empty");
            listArray[top++] = it;
        }
    
        E pop(){
            Assert(top != 0, "Stack is empty");
            return listArray[--top];
        }
    
        const E& topValue() const{
            Assert(top != 0, "Stack is empty");
            return listArray[top - 1];
        }
    
        int length() const{
            return top;
        }
    };

--------------------

## 链式栈的实现： ##

template <typename E> 
    class LStack : public Stack{
    private:
        Link<E>* top;
        int size;
    
    public:
        LStack(int sz = defaultSize){
            top = NULL;
            size = 0;
        }
    
        ~LStack(){
            clear();
        }
    
        void clear(){
            while (top != NULL){
                Link<E>* temp = top;
                top = top->next;
                delete temp;
            }
            size = 0;
        }
    
        void push(const E& it){
            top = new Link<E>(it, top);
            size++;
        }
    
        E pop(){
            Assert(top != NULL, "Stack is empty");
            E it = top->element;
            Link<E>* ltemp = top->next;
            delete top;
            top = ltemp;
            size--;
            return it;
        }
    
        const E& topValue() const{
            Assert(top != NULL, "Stack is empty");
            return top->element;
        }
    
        int length() const{
            return size;
        }
    };