前言

写在前面的话：数据结构与算法。

对于初识数据结构的小伙伴们，鉴于后面的数据结构的构建会使用到同tag前面的内容，包括具体数据结构的应用，所使用到的数据结构，也是自己构建的，未使用系统的库文件，因此，建议这类小伙伴们按顺序进行学习；

对于想查询有关资料的小伙伴们，可以选择性地浏览。希望大家都能有所收获～

栈的基本特点

上一篇我们介绍了链表，本章我们接着来看另外一种数据结构-----栈。

栈是一种非常重要的数据结构，在许多系统级的架构中，大量使用了栈。

栈的核心：后进先出（LIFO），简单说来，就是对于栈，我们只能操作栈顶元素（出栈，压栈等），我们可以从两个例子里理解栈的特点：

网页的回退操作

当浏览一个网页想回退时，你会发现回退的永远是上一次浏览的页面，而不是最开始打开的页面，这里面就用到了“后进先出”的思想。浏览器的底层实现中，把用户浏览的网页用“栈”这种数据结构缓存起来，一旦用户想要返回上一页（此处的“上一页”便是该栈的“栈顶元素”），直接调用栈顶元素即可。请读者仔细体会一下。

粘贴操作

同1一样的思想，系统在底层实现中，将待粘贴的内容用“栈”存储起来，这样能使得用户粘贴的内容，永远是最近一次复制的内容。

栈的结构实现

了解了栈的基本特点之后，我们来看看栈这种数据结构的代码实现。

学了前面的向量之后，构建一个栈非常容易。在这，笔者着重介绍栈的几个应用。

在应用之前，我们先来简单地构建一个栈：

下面的Stack.h继承了Vector类，Vector类来自于同tag下的Vector文章：

/*
 * 作者：易果啥笔
 * 时间：2021.8.20
 * 内容：栈的头文件
 *
 */

#ifndef STACK_STACK_H
#define STACK_STACK_H
#include "Vector.h"
template <typename T> class Stack: public Vector<T> {
    public:
        void push(T const& e){this->insert(this->size(),e);}//入栈
        T pop(){return this->remove(this->size()-1);}//删除栈顶元素，出栈
        T& top(){return (*this)[(this->size()-1)];} //取出栈顶元素
};
#endif //STACK_STACK_H

需要注意的是，

根据栈的特点，我们需要对Vector.h中的traverse方法修改一下，修改如下：

template <typename T> 
void Vector<T>::traverse(void (*visit)(T &)) {
    for(int i = _size-1 ; i >= 0 ; i--) visit(_elem[i]) ; //利用函数指针机制的遍历
}

后面，我们会着重介绍栈的几个应用。