栈的定义

只能在一端进行插入和删除操作：先进后出，后进先出。理解为一种受限的线性表。

允许进行插入和删除操作的一端称为栈顶——桶口（表尾）。

栈的顺序存储（顺序栈）：用一段连续的内存空间依次存储栈中的数据。

两种保存数据的方案：

•  通过为一维数组静态分配内存的方式来保存数据。
• 通过为一维数组动态分配内存的方式来保存数据。

为了考虑到元素存取的方便性，将数组下标为0的一端作为栈底最合适。

顺序栈

栈结构的定义：

    #define InitSize 10 //动态数组的初始尺寸#define IncSize  5 //当动态数组存满数据后每次扩容所能多保存的数据元素数量template  //T代表数组中元素的类型class SeqStack {public:SeqStack(int length = InitSize); //构造函数，参数可以默认值~SeqStack();   //析构函数public:bool Push(const T& e); //入栈（增加数据）bool Pop(T& e); //出栈（删除数据），也就是删除栈顶数据bool GetTop(T& e);     //读取栈顶元素，但该元素并没有出栈而是依旧在栈中void DispList(); //输出顺序栈中所有元素int ListLength(); //获取顺序栈的长度（实际拥有的元素数量）bool IsEmpty(); //判断顺序栈是否为空bool IsFull();  //判断顺序栈是否已满private:void IncreaseSize(); //当顺序栈存满数据后可以调用此函数为顺序栈扩容private:T* m_data;  //存放顺序栈中的元素int m_maxsize; //动态数组最大容量int m_top;  //栈顶指针（用作数组下标），指向栈顶元素，该值为-1表示空栈};

 实现栈里面的成员函数：

//通过构造函数对顺序栈进行初始化template SeqStack::SeqStack(int length){m_data = new T[length]; //为一维数组动态分配内存，该值和算法空间复杂度无关，空间复杂度一般指算法额外需要的存储空间。m_maxsize = length; //顺序栈最多可以存储m_maxsize个数据元素，超过了就要扩容了。m_top = -1; //空栈}//通过析构函数对顺序栈进行资源释放template SeqStack::~SeqStack(){delete[] m_data;}//入栈（增加数据），通常时间复杂度为O(1)，但一旦需要扩容，时间复杂度就会变成O(n)了template bool SeqStack::Push(const T& e){if (IsFull() == true){//cout << "顺序栈已满，不能再进行入栈操作了！" << endl;//return false;IncreaseSize(); //扩容}m_top++; //栈顶指针向后走m_data[m_top] = e; //和上行代码合并写成 m_data[++m_top] = e;return true;}//当顺序栈存满数据后可以调用此函数为顺序栈扩容，时间复杂度为O(n)template void SeqStack::IncreaseSize(){T* p = m_data;m_data = new T[m_maxsize + IncSize]; //重新为顺序栈分配更大的内存空间for (int i = 0; i <= m_top; ++i){m_data[i] = p[i]; //将数据复制到新区域}m_maxsize = m_maxsize + IncSize; //顺序栈最大长度增加IncSizedelete[] p; //释放原来的内存空间}//出栈（删除数据），也就是删除栈顶数据，时间复杂度O(1)template bool SeqStack::Pop(T& e){if (IsEmpty() == true){cout << "当前顺序栈为空，不能进行出栈操作！" << endl;return false;}e = m_data[m_top]; //栈顶元素值返回到e中。有的实现版本不会在Pop成员函数中返回栈顶元素，此时要取得栈顶元素需要用到GetTop()成员函数。m_top--; //本行和上行代码可以合并  e= m_data[m_top--];return true;}//读取栈顶元素，但该元素并没有出栈而是依旧在栈顶中，因此m_top值不会发生改变，时间复杂度O(1)template bool SeqStack::GetTop(T& e){if (IsEmpty() == true){cout << "当前顺序栈为空，不能进行读取栈顶元素！" << endl;return false;}e = m_data[m_top]; //栈顶元素返回到e中return true;}//输出顺序栈中所有元素，时间复杂度O(n）template void SeqStack::DispList(){//按照从栈顶到栈底的顺序来显示数据：for (int i = m_top; i >= 0; --i){cout << m_data[i] << "  ";  //每个数据之间以空格分隔}cout << endl; //换行}//获取顺序栈的长度（实际拥有的元素数量），时间复杂度O(1)template int SeqStack::ListLength(){return m_top + 1;//m_top是栈顶元素的下标，返回实际个数要➕1}//判断顺序栈是否为空，复杂度O(1)template bool SeqStack::IsEmpty(){if (m_top == -1)return true;return false;}//判断顺序栈是否已满，复杂度O(1)template bool SeqStack::IsFull(){if (m_top >= m_maxsize -1)return true;return false;}

链式栈

    //链式栈中每个节点的定义template  //T代表数据元素的类型struct StackNode{T  data; //数据域，存放数据元素StackNode* next; //指针域，指向下一个同类型（和本节点类型相同）节点}; //链式栈的定义template class LinkStack{public:LinkStack(); //构造函数~LinkStack(); //析构函数public:bool Push(const T& e); //入栈元素ebool Pop(T& e); //出栈（删除数据）操作，也就是删除栈顶数据bool GetTop(T& e); //读取栈顶元素，但该元素并没有出栈而是依旧在栈中void DispList(); //输出链式栈中的所有元素int ListLength(); //获取链式栈的长度bool Empty(); //判断链式栈是否为空private:StackNode* m_top; //栈顶指针int  m_length; //链式栈当前长度};

 类成员函数的实现：

    //构造函数，通过构造函数对链式栈进行初始化template LinkStack::LinkStack(){m_top = nullptr;m_length = 0;}    //入栈元素e，时间复杂度为O(1)template bool LinkStack::Push(const T& e){StackNode* node = new StackNode;node->data = e;node->next = m_top;m_top = node;m_length++;return true;}    //出栈（删除数据），也就是删除栈顶数据，时间复杂度O(1)template bool LinkStack::Pop(T& e){if (Empty() == true) //链式栈为空return false;StackNode* p_willdel = m_top;m_top = m_top->next;m_length--;e = p_willdel->data;delete p_willdel;return true;}    //读取栈顶元素，但该元素并没有出栈而是依旧在栈中template bool LinkStack::GetTop(T& e){if (Empty() == true) //链式栈为空return false;e = m_top->data;return true;}    //输出链式栈中的所有元素，时间复杂度O(n)template void LinkStack::DispList(){if (Empty() == true) //链式栈为空return;StackNode* p = m_top;while (p != nullptr){cout <data <next;}cout << endl; //换行}    //获取链式栈的长度，时间复杂度O(1)template int LinkStack::ListLength(){return m_length;}//判断链式栈是否为空，时间复杂度O(1)template bool LinkStack::Empty(){if (m_top == nullptr)return true;return false;}    //通过析构函数对链式栈进行资源释放template LinkStack::~LinkStack(){T tmpnousevlaue = { 0 };while (Pop(tmpnousevlaue) == true){} //把栈顶元素删光，while循环也就退出了，此时也就是空栈了}