《数据结构》期末提纲之栈

1.栈的简介

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。（百度百科）

2.栈的种类

• 顺序栈
  顺序栈即使用顺序表实现的栈。本博文中的顺序栈为顺序表的继承。关于顺序表请参见：《数据结构》期末提纲之顺序表
• 链栈
  链栈即使用链表实现的栈。本博文中的链栈为链表的继承。关于链表请参见：《数据结构》期末提纲之链表

3.栈的基本操作

• 入栈
  入栈，顾名思义，即讲数据存入栈中，通常以对线性表进行头插的方式实现。如图所示：（灵魂画师）
  
• 出栈
  出栈即弹出栈顶元素，一班通过对线性表表头元素进行返回并删除来实现。如图所示：
  
  栈只能对栈顶元素进行操作，所以其操作种类较少。

4.顺序栈的C++实现

由于顺序栈使限定操作的顺序表，所以其为顺序表的私有继承，特此声明。顺序表实现不在本博文赘述。传送门

• 类型构造

template<class DataType>
class SeqStack : private SeqList<DataType> //顺序栈类，为顺序表的私有继承
{
   
public:
    SeqStack(); //构造
    ~SeqStack(); //析构
    void push(DataType x); //从栈顶添加元素
    DataType top(); //访问栈顶
    void pop(); //删除栈顶
    int size(); //返回大小
    void clr(); //清空栈
};

• 构造与析构

template<class DataType> //会对线性表进行自动构造与析构，此处无需另外的操作
SeqStack<DataType>::SeqStack()
{
   
    cout << "SeqStack Constructed!" << endl;
}

template<class DataType>
SeqStack<DataType>::~SeqStack()
{
   
    cout << "SeqStack Distructed!" << endl;
}

• 入栈

template<class DataType>
void SeqStack<DataType>::push(DataType x)
{
   
    this->insert(this->