C++用模板实现栈

╰+哭是因爲堅強的太久メ 2022-09-26 02:30 133阅读 0赞

#ifndef _CStack 
    #define _CStack 
    #include<iostream.h> 
    template<class T>
    class CStack{
        // LIFO 对象 
    public:
        CStack(int MaxStackSize = 10);
        ~CStack() { delete[] stack; }
        bool IsEmpty() const { return top == -1; }
        bool IsFull() const { return top == MaxTop; }
        T Top() const;
        CStack<T>& Add(const T& x);
        CStack<T>& Delete(T& x);
        friend ostream& operator<<(ostream& out, const CStack<T>& w);
    
    private:
        int top; // 栈顶 
        int MaxTop; // 最大的栈顶值 
        T *stack; // 堆栈元素数组 
    };
    
    template<class T>
    CStack<T>::CStack(int MaxStackSize)
    {
       // CStack 类构造函数 
        MaxTop = MaxStackSize - 1;
        stack = new T[MaxStackSize];
        top = -1;
    }
    template<class T>
    T CStack<T>::Top() const
    {
       // 返回栈顶元素 
        if (!IsEmpty())
            return stack[top];
    }
    template<class T>
    CStack<T>& CStack<T>::Add(const T& x)
    { //添加元素x 
        if (!IsFull())
        {
            stack[++top] = x;
            return *this;
        }
    }
    
    template<class T>
    CStack<T>& CStack<T>::Delete(T& x)
    {
       // 删除栈顶元素，并将其送入x 
        if (!IsEmpty())
        {
            x = stack[top--];
            return *this;
        }
    }
    template <class T>
    ostream& operator<<(ostream& out, const CStack<T>& w)
    {
        for (int i = w.top; i > -1; i--)
            out << w.stack[i] << " ";
        return out;
    
    }
    
    
    /*采用链表来定义栈*/
    template<class T>class LinkedStack;
    template <class T>
    class Node{
        friend LinkedStack<T>;
    private:
        T data;
        Node<T> *link;
    };
    template<class T>
    class LinkedStack {
    public:
        LinkedStack() { top = 0; }
        ~LinkedStack();
        bool IsEmpty() const { return top == 0; }
        bool IsFull() const;
        T Top() const;
        LinkedStack<T>& Add(const T& x);
        LinkedStack<T>& Delete(T& x);
    private:
        Node<T> *top; // 指向栈顶节点 
    };
    
    template<class T>
    LinkedStack<T>:: ~LinkedStack()
    {
        // 析构函数 
        Node<T> *next;
        while (top) {
            next = top->link;
            delete top;
            top = next;
        }
    }
    template<class T>
    bool LinkedStack<T>::IsFull() const
    {
       // 堆栈是否满? 
        try {
            Node<T> *p = new Node<T>;
            delete p;
            return false;
        }
        catch (...) { return true; }
    }
    template<class T>
    LinkedStack<T>& LinkedStack<T>::Add(const T& x)
    {
       // 添加元素x 
        Node<T> *p = new Node<T>;
        p->data = x;
        p->link = top;
        top = p;
        return *this;
    }
    template<class T>
    T LinkedStack<T>::Top() const
    {
       // 返回栈顶元素 
        if (!IsEmpty())
            return top->data;
    }
    template<class T>
    LinkedStack<T>& LinkedStack<T>::Delete(T& x)
    {
       // 删除栈顶元素，并将其送入x 
        if (!IsEmpty())
        {
    
            x = top->data;
            Node<T> *p = top;
            top = top->link;
            delete p;
            return *this;
        }
    }
    #endif

//在主函数的调用如下：
    [cpp] view plain copy
    #include "Stack.h" 
    void main()
    {
        CStack<int> S(20);
        for (int i = 0; i < 20; i++)
            S.Add(i);
        cout << "栈顶元素为：" << S.Top() << endl;
        cout << "所有栈元素为：" << S << endl;
    }

转自：[http://blog.csdn.net/xiaoding133/article/details/6897101][http_blog.csdn.net_xiaoding133_article_details_6897101]

[http_blog.csdn.net_xiaoding133_article_details_6897101]: http://blog.csdn.net/xiaoding133/article/details/6897101