栈及其特点和应用（C++详解版）

像数组或链表一样，栈也是一种数据结构，它包含一系列元素。

但是，与数组和链表不同的是，栈是一个后进先出（LIFO）的结构，这意味着当一个程序从栈中检索元素时，插入到栈中的最后一个元素是第一个被检索的元素（同样，插入的第一个元素是最后一个被检索的元素）。

在想象一个栈的工作方式时，可以想象一下餐厅流水线开始时的一堆盘子。当餐厅的工作人员补充餐盘时，他或她放入的第一个盘子将是最后一个被取走的，如图 1 所示。

图 1 栈的后进先出方式就像餐厅盘子的取用方式

餐厅中一堆盘子的LIFO特性也是栈数据结构的主要特征。放在栈上的最后一个数据元素是从栈中检索的第一个数据。

有以下两种类型的栈数据结构：

1. 静态栈：又称"顺序栈"。具有固定大小，并以数组形式实现；
2. 动态栈：又称"链栈"。可根据需要增长，并以链表形式实现；

栈的应用

如果某个算法需要首先处理序列中最后保存的元素，那么栈对于这种算法而言是非常有用的数据结构。

例如，计算机系统在执行程序时就会使用栈。当某个函数被调用时，计算机系统会将程序的返回地址、函数的参数以及函数的局部变量保存在栈中。当函数返回时，这些局部变量、参数和返回的地址等都将被从栈上删除。

栈操作

栈有两个主要操作：入栈（push，也被称为压栈）和出栈（pop，也被称为弹栈）。

入栈操作会导致一个值被存储，或者被压入栈。例如，假设有一个空的整数栈，最多可以保存 3 个值。有了这个栈，则可以执行以下入栈操作：

图 2 显示了在执行这些入栈操作之后的栈状态。

图 2 入栈操作图解

出栈操作将从栈中检索（继而删除）一个值。假设要在如图 2 所示的栈上执行 3 个连续的出栈操作，结果将如图 3 所示。

图 3 出栈操作图解

从图 3 可以看出，最后的出栈操作可将栈清空。

对于静态和动态栈，都需要一个布尔 isEmpty 操作。当栈为空时，isEmpty 操作返回 true，否则返回 false。通过调用该操作，程序员可以在尝试执行出栈操作之前确认栈上有东西。