栈及其特点和应用(C++详解版)

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

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

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

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

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

有以下两种类型的栈数据结构:
  1. 静态栈:又称"顺序栈"。具有固定大小,并以数组形式实现;
  2. 动态栈:又称"链栈"。可根据需要增长,并以链表形式实现;

栈的应用

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

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

栈操作

栈有两个主要操作:入栈(push,也被称为压栈)和出栈(pop,也被称为弹栈)。

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

push(5);
push(10);
push(15);

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

入栈操作图解
图 2 入栈操作图解

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


图 3 出栈操作图解

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

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