堆栈和LIFO结构:实现和用例

很少有数据结构像堆栈那样普遍存在。 它们易于理解和实现,但它们的强大之处在于强大。 本文的目的是解释什么是堆栈以及如何实现堆栈,并介绍三个实际用例。 让我们开始吧!

此处 克隆本文随附的存储库

说明:堆栈与数组

堆栈是一种结构,负责遵循LIFO原理(后进先出)动态地收集数据。 打个比方,您可以想象一堆自助餐厅托盘:当您要添加一个新托盘时,它将被引入到堆叠顶部(而不是插入其中)。 由于最后一个纸盘在纸堆的顶部,因此当需要一个单独的纸盘时,它也将是第一个脱落的纸盘。 堆栈提供两个主要功能:“推动”或引入一个新元素,以及“弹出”或除去最后一个元素。

如果我们将此结构与典型数组进行比较,就会发现一些明显的区别。 尽管Swift会以智能方式处理数组的内存分配,但在基础语言中,数组容量是在初始化期间设置的,并且是静态的。 另一方面,堆栈根据需要为单个节点分配和取消分配内存,这使它们非常灵活。 此外,数组允许访问任何索引的元素,而堆栈仅与终端节点进行交互。 尽管这似乎很有限(确实是……),但它实际上使数据访问非常轻巧且快速。 此外,LIFO行为对于解决特定情况可能非常有用,我们将在本文后面介绍。

堆栈:演示实现

有几种方法可以实现堆栈,但是在本演示中,我们将创建一个双向链接列表,该列表清楚地演示了在引入新元素时的动态内存分配。 首先,让我们仅查看所需的类和属性:

接下来,让我们看一下如何新元素压入堆栈。 步骤1:使用所需的值创建一个新节点。 步骤2:假设endNode指向一个节点,我们可以将端节点中的下一个属性分配给新节点,并将新节点中的前一个属性分配回端节点。 请记住,先前的属性很弱,因此我们避免了保留周期。 步骤3:最后,我们可以通过访问endNode的next属性将其endNode指针移至newNode。 请注意,列表所需的内存随着newNode的分配和初始化而增长。

我们的pop()方法删除端节点并返回该节点中的值。 步骤1:我们将值存储在端节点的临时常量val中 。 步骤2:我们通过使用endNode指针的先前属性将其向后移动一个元素。 步骤3:我们将endNodes的next属性设置为nil。 现在,最后两个节点之间的唯一参考是通过标记为弱的先前属性。 这意味着从内存中释放了该节点。 步骤4:我们返回最后一个节点中的值。

在解释了这些重要方法之后,让我们看一下Stack类的最终实现:

pushpop方法的出现与我们期望的完全一样(第13–32行) 。 我们可以使用push方法创建带有一些可变参数值的自定义初始化程序(第7-11行)。 另外,我们可以通过检查rootNode是否具有值(第34–36行)并具有基本的打印方法(只要它能够通过下一个属性访问节点)来遍历列表(第38–36行) ,以检查堆栈是否为空。 44)

我们的堆栈功能的基本测试如下所示:

知道如何实现堆栈是一回事,但更重要的是识别适合堆栈的情况。 在下一部分中,我们将研究三种此类情况。

用例1:冲销订单

因为堆栈的顺序是固定的,所以通过将元素从一个堆栈弹出并立即放在另一个堆栈上可以非常容易地实现逆序。 不用乱搞索引!

用例2:测试对称性

堆栈的另一个好用例是测试对称性。 在下面的示例中,我们正在测试一串括号,以确保每个闭合括号与先前的打开括号正确匹配。

我们首先检查字符数是否可以被不整数(第6行)立即除以2的奇数个字符。 接下来,我们通过定义一个非法字符字符集来检查我们是否具有有效的输入,然后检查我们的输入字符串是否包含零个非法字符范围(第7-8行) 。 为了检查左括号和右括号是否匹配,我们将它们作为键值对放入字典中(第10行)在其他情况下,您可以计算逆值而不必将对存储在字典中 。 然后我们有了堆栈(第11行) 。 在这种情况下,我们堆叠的目的是存放开口支架。 当我们遍历String时,可以通过测试字符是否是字典中的键来检查字符是否为开括号。 如果是,我们将其压入堆栈。 一旦找到第一个闭合括号,我们就知道我们正在处理模式的后半部分,因此我们将firstHalf布尔值设置为false (第12行) 。 如果在此之后发现更多的方括号,我们可以检查布尔值并指示测试失败。 对于每个右括号,我们弹出最后一个左括号,并检查它们是否为正确的键值对。 再一次,我们只需要遍历字符串一次,因此我们从线性算法中获得了很多价值。

用例3:撤消命令

最后,我们将结合使用堆栈和命令pattern来创建撤消历史记录。 首先,让我们看一个简单的银行帐户对象。 它具有余额和透支额度以及一些简单的存款和取款方法:

可以直接在命令中存储相关信息,而不是直接调用deposit和withdraw方法。 在下面的代码段中,我们使用枚举属性(存款或提款)和一个数量指定要执行的操作类型。 我们还存储一个布尔值以指示命令是否能够执行(第4-11行) 。 请注意,如果提款请求超出透支限额,则银行帐户将不会发生任何事情,并且成功的布尔值将保持为false,否则一旦命令完成将变为true( 第18–26行) 。 我们有两种方法来调用或撤消命令,每种方法都以银行帐户作为参数(第18和28行) 。 这些方法使用银行帐户并调用我们在上一片段中看到的实例方法。

回到银行帐户 ,我们现在可以介绍我们的commandStack属性,该属性已经用BankAccountType初始化(第47行) 。 我们将我们的存款和提款方法标记为fileprivate 这样它们只能由我们的BankAccountCommand访问(第62和66行) 。 现在,我们有两个公开的方法: process(command 🙂undoLastCommand() 。 第一个接受命令作为输入,使用银行帐户作为输入执行该命令,然后将命令压入堆栈。 同时,undoLastCommand方法将最后一个命令弹出堆栈并执行撤消(第51-60行)

这是一种非常简单的模式,并且功能非常强大。 可能的应用是无穷无尽的,并为用户提供了令人满意的体验。

现在,让我们看看实际的模式:

在本文中,我们探讨了堆栈和LIFO行为的概念。 我们使用双链表实现了自己的堆栈,并演示了如何随着堆栈大小的变化分配和释放内存。 我们还研究了三种常见的堆栈用例:反转,测试对称性和撤消。 在现实世界中,这三种情况中的每一种都会无数次出现。 我希望您会认为堆栈是处理这些需求的适当结构。 与往常一样,感谢您的阅读!