C++实现整型栈（附部分解析和源码）

定义一个My_Stack类，类中的属性有_data(用来存放栈内元素)，_size（栈的大小），_top(栈顶)，定义栈的初始大小为10，增量为2

类中属性：

    int _size;
    int *_data;
    int _top;

写出构造函数：

   My_Stack(const int sz = STACK_INIT_SIZE)
        : _size(sz),_data(new int[_size]), _top(-1){}

或

    My_Stack(const int sz = STACK_INIT_SIZE)
        : _size(sz),_data(nullptr), _top(-1)
    {
        _data = new int[_size];
    }

或

    My_Stack(const int sz = STACK_INIT_SIZE)
        : _size(sz),_data(nullptr), _top(-1)
    {
        _data = (int*)malloc(sizeof(int) * _size);
        if (nullptr == _data)
        {
            exit(1);
        }
    }

（注意：成员初始化的顺序是按照类型中设计的顺序进行的，和初始化列表顺序无关）

当构建一个对象st时，系统空间分配如图：

析构函数（释放资源）：

   ~My_Stack()
    {
        free(_data);//如果用new申请的空间，释放时使用delete [ ]_data;
        _data = nullptr;//释放后将指针置为空，否则指针失效

        _size = 0;
        _top = -1;
    }

入栈过程：

入栈时首先要判断栈是否满了，当元素个数等于容量时，栈满，扩容。出栈时判断栈是否为空，出栈_top--。

入栈：

 bool push(const int val)
    {
        if (full())
        {
            return false;
        }
        _top += 1;
        _data[_top] = val;
        return true;
    }

出栈：

    void pop()
    {
        if (empty())
        {
            cout << "stack empty" << endl;
        }
        _top -= 1;
    }

全部代码如下：

#include
#include
#include
#include
#include

using namespace std;
enum { STACK_INIT_SIZE = 10, STACK_ISC_SIZE = 2 };

class My_Stack
{
private:
    int _size;
    int* _data;
    int _top;
public:
    //构造函数
    My_Stack(const int sz = STACK_INIT_SIZE)
        : _size(sz),_data(nullptr), _top(-1)
    {
        _data = (int*)malloc(sizeof(int) * _size);
        if (nullptr == _data)
        {
            exit(1);
        }
    }

    //析构函数
    ~My_Stack() 
    {
        free(_data);
        _data = nullptr;
        _size = 0;
        _top = -1;
    }
    //判断是否为空
    bool empty()const
    {
        return size() == 0;
    }
    //判断是否为满
    bool full() const
    {
        return size() == capc();
    }
    bool resize(size_t newsz)
    {
        if (newsz <= capc())
        {
            return true;
        }
        int* newdata = (int*)realloc(_data, sizeof(int) * newsz);
        if (nullptr == newdata)return false;
        _data = newdata;
        _size = newsz;
        return true;
    }
    //获取栈中元素个数
    int size()const
    {
        return _top + 1;
    }
    //得到栈的容量大小
    int capc()const
    {
        return _size;
    }
    //入栈
    bool push(const int val)
    {
        if (full()&&resize(capc()*STACK_ISC_SIZE))
        {
            return false;
        }
        _top += 1;
        _data[_top] = val;
        return true;
    }
    //出栈
    void pop()
    {
        if (empty())
        {
            cout << "stack empty" << endl;
        }
        _top -= 1;
    }
    //取栈顶元素，但不出栈
    int top()const
    {
        assert(!empty());
        return _data[_top];
    }
    //取栈顶元素并且出栈
    int gettop()
    {
        assert(!empty());
        return _data[_top--];
    }
};

int main()
{
    My_Stack st;
    st.resize(200);//效率更高，不需要反复增容
    for (int i = 0; i <100; ++i)
    {
        st.push(i);
    }
    while (!st.empty())
    {
        int x = st.gettop();
        cout << x << endl;
    }
    return 0;
}

若不仅仅想实现整型栈，还想在栈中放入double类型、char类型不同类型的数据，可以用模版来实现，代码如下：

#include
#include
#include
#include
#include

using namespace std;
enum { STACK_INIT_SIZE = 10, STACK_ISC_SIZE = 2 };
template 
class My_Stack
{
private:
    int _size;
    T * _data;
    int _top;
public:
    //构造函数
    My_Stack(const int sz = STACK_INIT_SIZE)
        : _size(sz),_data(nullptr), _top(-1)
    {
        _data = (T*)malloc(sizeof(T) * _size);
        if (nullptr == _data)
        {
            exit(1);
        }
    }

    //析构函数
    ~My_Stack() 
    {
        free(_data);
        _data = nullptr;
        _size = 0;
        _top = -1;
    }
    //判断是否为空
    bool empty()const
    {
        return size() == 0;
    }
    //判断是否为满
    bool full() const
    {
        return size() == capc();
    }
    bool resize(size_t newsz)
    {
        if (newsz <= capc())
        {
            return true;
        }
        T* newdata = (T*)realloc(_data, sizeof(T) * newsz);
        if (nullptr == newdata)return false;
        _data = newdata;
        _size = newsz;
        return true;
    }
    //获取栈中元素个数
    T size()const
    {
        return _top + 1;
    }
    //得到栈的容量大小
    T capc()const
    {
        return _size;
    }
    //入栈
    bool push(const T val)
    {
        if (full()&&resize(capc()*STACK_ISC_SIZE))
        {
            return false;
        }
        _top += 1;
        _data[_top] = val;
        return true;
    }
    //出栈
    void pop()
    {
        if (empty())
        {
            cout << "stack empty" << endl;
        }
        _top -= 1;
    }
    //取栈顶元素，但不出栈
    T top()const
    {
        assert(!empty());
        return _data[_top];
    }
    //取栈顶元素并且出栈
    T gettop()
    {
        assert(!empty());
        return _data[_top--];
    }
};

int main()
{
    My_Stack st;
    st.resize(200);
    
    for(char i = 'A'; i <= 'Z'; ++i)
    {
        st.push(i);
    }
    while (!st.empty())
    {
        char x = st.gettop();
        cout << x << endl;
    }
    return 0;
}