数据结构——基本栈的模板类

心已赠人 2022-06-07 02:57 255阅读 0赞

**数据结构笔记**  
这篇文章主要是给出栈的基本操作的代码（如： POP、PUSH等），是一个最基本的栈的模板类。

#include <iostream>
    #include <cassert>
    #include "stack.h"
    using namespace std;
    const int stackIncreament = 20;                             //栈溢出时扩展空间的增量
    
    template<class T>
    class SeqStack :public Stack<T> {
    public:
        SeqStack(int sz = 50);                                  //建立一个空栈
        ~SeqStack();                                           //析构函数
        void Push(const T & x);                                 //如果IsFull则溢出处理，否则把x推入栈顶
        bool Pop(T & x);                                        //如果IsEmpty则不执行，返回false，否则推掉栈顶元素并返回true
        //推出元素值通过引用参数x返回
        bool getTop(T & x)const;                                //如果栈为NULL则返回false，否则返回true，栈顶元素的值通过x传回
        bool IsEmpty()const;                                    //如果栈中元素等于0个返回true，否则返回false
        bool IsFull()const;                                     //如果栈中元素等于maxSize，返回true，否则返回false
        int getSize()const;                                     //返回栈中元素的个数
        void makeEmpty();                                       //清空栈的内容
        void output(ostream & os);
    private:
        T *elements;                                            //存放栈中元素的栈数组
        int top;                                                //标记栈的top
        int maxSize;                                            //栈的最大能容元素的个数
        void overflowProcess();                                 //栈的溢出处理
    };
    
    template<class T>
    void SeqStack<T>::output(ostream & os) {
        os << "top = " << top << endl;
        for (int i = 0; i <= top; i++) {
            os << i << ":" << elements[i] << endl;
        }
    }
    
    template<class T>
    ostream & operator << (ostream & os, SeqStack<T> & s) {
        s.output(os);
        return os;
    }
    
    template<class T>
    SeqStack<T>::~SeqStack() {
        delete[] elements;
    }
    
    template<class T>
    bool SeqStack<T>::IsEmpty() const {
        //判断是否为NULL
        if (-1 == top) {
            return true;
        }
        else {
            return false;
        }
    }
    
    template<class T>
    bool SeqStack<T>::IsFull() const {
        //判断栈是否FULL
        if (maxSize - 1 == top) {
            return true;
        }
        else {
            return false;
        }
    }
    
    template<class T>
    void SeqStack<T>::makeEmpty() {
        //清空栈
        top = -1;
    }
    
    template<class T>
    int SeqStack<T>::getSize()const {
        return top + 1;
    }
    
    template<class T>
    SeqStack<T>::SeqStack(int sz) {
        top = -1;
        maxSize = sz;
        //建立一个最大尺寸为sz的空栈，若分配不成功则错误处理
        elements = new T[maxSize];                              //创建栈的数组空间  
        assert(elements != NULL);                               //断言：动态存储分配是否成功
    }
    
    template<class T>
    void SeqStack<T>::overflowProcess() {
        //私有函数：扩充栈的存储空间
        T * newArray = new T[maxSize + stackIncreament];
        if (NULL == newArray) {
            cerr << "内存分配错误" << endl;
            exit(1);
        }
        for (int i = 0; i <= top; i++) {
            newArray[i] = elements[i];                          //将原来栈中的数据逐一copy
        }
        maxSize += stackIncreament;                             //更新栈的最大容量
        delete[] elements;                                      //释放原来的指针
        elements = newArray;                                    //更新原来的指针
    }
    
    template<class T>
    void SeqStack<T>::Push(const T& x) {
        //若栈不满，则将元素x推入栈顶位置，否则溢出处理
        if (IsFull()) {
            overflowProcess();                                  //检测到栈满，扩充栈的容量
        }
        elements[++top] = x;                                    //先执行top+1，后元素进栈
    }
    
    template<class T>
    bool SeqStack<T>::Pop(T & x) {
        //若栈不空则函数返回栈顶的值，并将栈顶元素弹出
        if (IsEmpty()) {
            return false;
        }
        x = elements[top--];                                    //top-1实现pop栈顶元素
        return true;
    }
    
    template<class T>
    bool SeqStack<T>::getTop(T &x)const {
        //若栈不空，则函数返回栈顶元素
        if (IsEmpty()) {
            return false;
        }
        x = elements[top];
        return true;
    }

int main()
    {
        int pop1, pop2;
        SeqStack<int> stackTest;
        stackTest.Push(1);
        stackTest.Push(2);
        stackTest.Push(2);
        stackTest.Push(2);
        stackTest.Push(5);
        cout << stackTest;
        stackTest.Pop(pop1);
        stackTest.Pop(pop2);
        cout << stackTest;
        cout << stackTest.getSize() << endl;
        int top;
        stackTest.getTop(top);
        cout << top << endl;
    
        system("pause");
        return 0;
    }

运行测试：![这里写图片描述][SouthEast]  
在写这部分程序中，应该注意的是对输出操作符的重载，在涉及友元函数及其它方式时应该注意的问题，之后会有相应的总结。

[SouthEast]: /images/20220607/b3ddf17c737c4a78a9829f4c47fb7b9a.png