数据结构（面向对象方法与C++语言描述）（第2版）顺序栈和链式栈内容整理
栈
栈（stack）可定义为只允许在表的末端进行插入和删除的线性表。允许插入和删除的一端叫做栈顶（top），而不允许插入和删除的另一端叫做栈底（bottom）。当栈中没有任何元素时，则成为空栈。
设给定栈 S =（a1，a2，……，an），则称最后加入栈中的元素为栈顶。栈中按a1，a2，……，an的顺序进栈。而退栈的顺序反过来，an先退出，然后an-1才能退出，最后退出a1。换句话说，后进者先出。因此，栈又叫座后进先出（LIFO，Last In First Out）的线性表。
栈的抽象数据类型有两种典型的存储表示：基于数组的存储表示和基于链表的存储表示。基于数组的存储表示实现的栈称为顺序栈，基于链表的存储表示实现的称为链式栈。
顺序栈
顺序栈可以采用顺序表作为其存储表示，为此，可以再顺序栈中的声明中用顺序表定义它的存储空间。为简化问题起见，使用一维数组作为栈的存储空间。存放栈元素的数组的头指针为* elements,该数组的最大允许存放元素个数为 maxSize，当前栈顶位置由数组下标指针 top 指示。如果栈不空时 elements[0]是栈中第一个元素。
链式栈
链式栈是线性表的链式存储表示。采用链式栈来表示一个栈，便于结点的插入与删除。在程序中同时使用多个栈的情况下，用链接表示不仅能够提高效率，还可以达到共享存储空间的目的。
代码实现
环境：vs2019
头文件：Stack.h
源文件：main.cpp
Stack.h代码：
#pragma onceconst int maxSize = 50;template<typename T>
class Stack { //栈的类定义
public:Stack() {}; //构造函数virtual void Push(const T& x) = 0; //新元素x进栈virtual bool Pop(T& x) = 0; //栈顶元素出栈，由x返回virtual bool getTop(T& x) const = 0; //读取栈顶元素，由x返回virtual bool IsEmpty() const = 0; //判断栈空否virtual bool IsFull() const = 0; //判断栈满否virtual int getSize() const = 0; //计算栈中元素个数
};
SeqStack.hpp代码：
#pragma once#include <iostream>
#include <cassert>
#include "Stack.h"using std::cerr;
using std::cout;
using std::endl;
using std::ostream;const int stackIncreament = 20; //栈溢出时扩展空间增量template<typename T>
class SeqStack :public Stack<T> { //顺序栈的类定义
public:SeqStack(int sz = 50); //建立一个空栈~SeqStack() { delete[] elements; } //析构函数void Push(const T& x); //如果IsFull()，则溢出处理；否则把x插入到栈的栈顶。bool Pop(T& x); //如果IsEmpty()，则不执行退栈，返回false；否则退掉位于栈顶的元素，返回true；//退出的元素值通过引用型参数x返回bool getTop(T& x) const; //如果IsEmpty()，则返回false；否则返回true，并通过引用型参数x得到栈顶元素的值。bool IsEmpty() const { return (top == -1) ? true : false; }//如果栈中元素个数等于0，则返回true，否则返回false。bool IsFull() const { return (top == maxSize - 1) ? true : false; }//如果栈中元素个数等于maxSize则返回true，否则返回false。int getSize() const { return top + 1; } //函数返回栈中元素个数。void MakeEmpty() { top = -1; } //清空栈中内容template<typename T>friend ostream& operator<<(ostream& os, SeqStack<T>& s);//输出栈中元素的重载操作<<
private:T* elements; //存放栈中元素的栈数组int top; //栈顶指针int maxSize; //栈最大可容纳元素个数void overflowProcess(); //栈的溢出处理
};template<typename T>
inline SeqStack<T>::SeqStack(int sz):top(-1), maxSize(sz)
{//建立一个最大尺寸为sz的空栈，若分配不成功则错误处理。elements = new T[maxSize]; //创建栈的数组空间assert(elements != nullptr); //断言：动态存储分配成功与否
}template<typename T>
inline void SeqStack<T>::Push(const T& x)
{//公共函数：若栈不满，则将元素x插入到该栈的栈顶，否则溢出处理。if (IsFull() == true) overflowProcess(); //栈满则溢出处理elements[++top] = x; //栈顶指针先加1，在进栈
}template<typename T>
inline bool SeqStack<T>::Pop(T& x)
{//公共函数：若栈不空则函数返回该栈栈顶元素的值，然后栈顶指针退1。if (IsEmpty() == true) return false; //判栈空否，若栈空则函数返回x = elements[top--]; //栈顶指针退1return true; //退栈成功
}template<typename T>
inline bool SeqStack<T>::getTop(T& x) const
{//公共函数：若栈不空则函数返回该栈栈顶元素的地址。if (IsEmpty() == true) return false; //判栈空否，若栈空则函数返回x = elements[top]; //返回栈顶元素的值return true;
}template<typename T>
inline void SeqStack<T>::overflowProcess()
{//私有函数：扩充栈的存储空间。T* newArray = new T[maxSize + stackIncreament];if (newArray == nullptr) { cerr << "存储分配失败！" << endl; exit(1); }for (int i = 0; i <= top; i++) newArray[i] = elements[i];maxSize = maxSize + stackIncreament;delete[] elements;elements = newArray;
}template<typename T>
ostream& operator<<(ostream& os, SeqStack<T>& s)
{//输出栈中元素的重载操作<<。os << "top = " << s.top << endl; //输出栈顶元素for (int i = 0; i <= s.top; i++) //逐个输出栈中元素os << i << ":" << s.elements[i] << endl;return os;
}
LinkedList.hpp代码:
#pragma once#include <iostream>template<typename T>
struct LinkNode { //链表结点的定义T data; //数据域LinkNode<T>* link; //链指针域LinkNode(LinkNode<T>* ptr = nullptr) { link = ptr; } //仅初始化指针成员的构造函数LinkNode(const T& item, LinkNode<T>* ptr = nullptr) //初始化数据与指针成员的构造函数{data = item;link = ptr;}
};template<typename T>
class List {
public:List() { first = new LinkNode<T>; } //构造函数List(const T& x) { first = new LinkNode<T>(x); } //构造函数List(List<T>& L); //拷贝构造函数~List() { makeEmpty(); } //析构函数void makeEmpty(); //将链表置为空表int Length()const; //计算链表的长度LinkNode<T>* getHead()const { return first; } //返回附加头结点地址LinkNode<T>* Search(T x); //搜索含数据x的元素LinkNode<T>* Locate(int i)const; //搜索第i个元素的地址bool getData(int i, T& x)const; //取出第i个元素的地址void setData(int i, T& x); //用x修改第i个元素的值bool Insert(int i, T& x); //在第i个元素后插入xbool Remove(int i, T& x); //删除第i个元素，x返回该元素的值bool IsEmpty()const //判表空否？空则返回true{return first->link == nullptr ? true : false;}bool IsFull()const { return false; } //判表满否？不满则返回falsevoid Sort(); //排序void input(); //输入void output(); //输出List<T>& operator=(List<T>& L); //重载运算符=void inputFront(T endTag); //前插法建立单链表void inputRear(T endTag); //后插法建立单链表
protected:LinkNode<T>* first; //链表的头指针
};template<typename T>
inline List<T>::List(List<T>& L)
{//拷贝构造函数T value;LinkNode<T>* srcptr = L.getHead(); //被赋值表的附加头结点地址LinkNode<T>* destptr = first = new LinkNode<T>;while (srcptr->link != nullptr) //逐个结点复制{value = srcptr->link->data;destptr->link = new LinkNode<T>(value);destptr = destptr->link;srcptr = srcptr->link;}destptr->link = nullptr;
}template<typename T>
inline void List<T>::makeEmpty()
{//将链表置位空表LinkNode<T>* q;while (first->link != nullptr) //当链不空时，删去链中所有结点{q = first->link;first->link = q->link; //保存被删结点，从链上摘下该节点delete q; //删除（仅保留一个表头节点）}
}template<typename T>
inline int List<T>::Length() const
{//计算带附加头结点的单链表的长度LinkNode<T>* p = first->link;int count = 0;while (p != nullptr) //循链扫描，寻找链尾{p = p->link;count++;}return count;
}template<typename T>
inline LinkNode<T>* List<T>::Search(T x)
{//在表中搜索含数据x的节点，搜索成功时函数返回该节点地址；否则返回NULL值。LinkNode<T>* current = first->link;while (current != nullptr){if (current->data == x) break; //循链找含x结点else current = current->link;}return current;
}template<typename T>
inline LinkNode<T>* List<T>::Locate(int i) const
{//定位函数。返回表中第i个元素的地址。若i<0或i超过表中结点个数，则返回NULL。if (i < 0) return nullptr; //i不合理LinkNode<T>* current = first;int k = 0;while (current != nullptr && k < i) //循链找第i个结点{current = current->link;k++;}return current; //返回第i个结点地址，若返回NULL，表示i值太大
}template<typename T>
inline bool List<T>::getData(int i, T& x) const
{//取出链表中第i个元素的值。if (i <= 0) return false; //i值太小LinkNode<T>* current = Locate(i);if (current == nullptr) return false; //i值太大else{x = current->data;return true;}
}template<typename T>
inline void List<T>::setData(int i, T& x)
{//给链表中的第i个元素赋值x。if (i <= 0) return; //i值太小LinkNode<T>* current = Locate(i);if (current == nullptr) return; //i值太大else current->data = x;
}template<typename T>
inline bool List<T>::Insert(int i, T& x)
{//将新元素x插入在链表中第i个结点之后。LinkNode<T>* current = Locate(i);if (current == nullptr) return false; //插入不成功LinkNode<T>* newNode = new LinkNode<T>(x);if (newNode == nullptr){std::cerr << "存储分配错误！" << std::endl;exit(1);}newNode->link = current->link;current->link = newNode;return true; //插入成功
}template<typename T>
inline bool List<T>::Remove(int i, T& x)
{//将链表中的第i个元素扇区，通过引用型参数x返回该元素的值。LinkNode<T>* current = Locate(i - 1);if (current == nullptr || current->link == nullptr) return false;//删除不成功LinkNode<T>* del = current->link; //重新拉链，将被删结点从链中摘下current->link = del->link;x = del->data;delete del; //取出被删结点中的数据值return true;
}template<typename T>
inline void List<T>::Sort()
{
}template<typename T>
inline void List<T>::input()
{
}template<typename T>
inline void List<T>::output()
{//单链表的输出函数：将单链表中所有数据按逻辑顺序输出到屏幕上。std::cout << "链表中的元素为：" << std::endl;LinkNode<T>* current = first->link;while (current != nullptr){std::cout << current->data << " ";current = current->link;}std::cout << std::endl;
}template<typename T>
inline List<T>& List<T>::operator=(List<T>& L)
{//重载函数：赋值操作，形式如 A = B，其中 A 是调用此操作的List对象，B 是参数表中的//引用型参数L结合的实参。makeEmpty();T value;LinkNode<T>* srcptr = L.getHead(); //被复制表的附加头结点地址LinkNode<T>* destptr = first = new LinkNode<T>;while (srcptr->link != nullptr) //逐个结点复制{value = srcptr->link->data;destptr->link = new LinkNode<T>(value);destptr = destptr->link;srcptr = srcptr->link;}destptr->link = nullptr;return *this; //返回操作对象地址
}template<typename T>
inline void List<T>::inputFront(T endTag)
{//endTag是约定的输入序列结束的标志。如果输入序列是正整数，endTag可以是0或负数；//如果输入序列是字符，endTag可以是字符集中不会出现的字符，如"\0"。LinkNode<T>* newNode;T val;makeEmpty();std::cin >> val;while (val != endTag){newNode = new LinkNode<T>(val); //创建新结点if (newNode == nullptr){std::cerr << "存储分配错误！" << std::endl;exit(1);}newNode->link = first->link;first->link = newNode; //插入到表最前端std::cin >> val;}
}template<typename T>
inline void List<T>::inputRear(T endTag)
{//endTag是约定的输入序列结束的标志LinkNode<T>* newNode, * last;T val;makeEmpty();std::cin >> val;last = first;while (val != endTag) //last指向表尾{newNode = new LinkNode<T>(val);if (newNode == nullptr){std::cerr << "存储分配错误！" << std::endl;exit(1);}last->link = newNode;last = newNode;std::cin >> val; //插入到表末端}last->link = nullptr; //表首位，这一句实际可省略
}LinkedStack.hpp代码：
#pragma once#include <iostream>
#include "Stack.h"
#include "LinkedList.hpp"using std::ostream;
using std::cout;
using std::endl;template<typename T>
class LinkedStack :public Stack<T> { //链式栈类定义
public:LinkedStack() :top(nullptr) { } //构造函数，置空栈~LinkedStack() { makeEmpty(); } //析构函数 void Push(const T& x); //进栈bool Pop(T& x); //出栈bool getTop(T& x) const; //读取栈顶元素bool IsEmpty() const { return (top == nullptr) ? true : false; }bool IsFull() const { return false; }int getSize() const; //求栈的元素个数void makeEmpty(); //清空栈的内容template<typename T>friend ostream& operator<<(ostream& os, LinkedStack<T>& s);//输出栈中元素的重载操作<<
private:LinkNode<T>* top; //栈顶指针，即链头指针
};template<typename T>
inline void LinkedStack<T>::Push(const T& x)
{//将元素值x插入到链式栈的栈顶，即链头。top = new LinkNode<T>(x, top); //创建新的含x结点assert(top != nullptr); //创建新结点失败退出
}template<typename T>
inline bool LinkedStack<T>::Pop(T& x)
{//删除栈顶结点，返回被删栈顶元素的值。if (IsEmpty() == true) return false; //若栈空则不退栈，返回LinkNode<T>* p = top; //否则暂存栈顶元素top = top->link; //栈顶指针退到新的栈顶位置x = p->data;delete p; //释放结点，返回退出元素的值return false;
}template<typename T>
inline bool LinkedStack<T>::getTop(T& x) const
{//返回栈顶元素的值if (IsEmpty() == true) return false; //若栈空则返回falsex = top->data; //栈不空则返回栈顶元素的值return true;
}template<typename T>
inline int LinkedStack<T>::getSize() const
{LinkNode<T>* p = top;int k = 0;while (p != nullptr){p = p->link;k++;}return k;
}template<typename T>
inline void LinkedStack<T>::makeEmpty()
{//逐次删去链式栈中的元素直至栈顶指针为空。LinkNode<T>* p;while (top != nullptr) //逐个结点释放{p = top;top = top->link;delete p;}
}template<typename T>
ostream& operator<<(ostream& os, LinkedStack<T>& s)
{//输出栈中元素的重载操作<<os << "栈中元素个数 = " << s.getSize() << endl; //输出栈中元素个数LinkNode<T>* p = s.top;int i = 0;while (p != nullptr) //逐个输出栈中元素的值{os << ++i << ":" << p->data << endl;p = p->link;}return os;
}
main.cpp代码：
#include "SeqStack.hpp"
#include "LinkedStack.hpp"int main()
{SeqStack<int> s1;cout << "栈s1的元素个数为：" << s1.getSize() << endl;s1.Push(10);s1.Push(20);s1.Push(30);cout << "栈s1的元素个数为：" << s1.getSize() << endl;cout << s1;LinkedStack<int> s2;cout << "栈s2的元素个数为：" << s2.getSize() << endl;s2.Push(10);s2.Push(20);s2.Push(30);cout << "栈s2的元素个数为：" << s2.getSize() << endl;cout << s2;return 0;
}
控制台界面：
![贤鱼的刷题日常--P2671 [NOIP2015 普及组] 求和](https://img-blog.csdnimg.cn/45349679fc4748499d6fd459d6b885f9.gif)
