使用链表实现堆栈

在第 3 章 "使用链接表" 中，我们学习了如何实现链接表。我们看到，在一个链表中，我们可以在末尾插入一个节点、从末尾移除一个节点、在链表中间插入一个节点、在开头插入一个节点等等。如果我们考虑单个链表数据结构的末尾插入和末尾移除操作，我们可以很容易地在栈中执行类似的操作。因此，让我们使用上一章中的 LinkedList 类来实现堆栈。代码如下所示：

Unresolved include directive in modules/ROOT/pages/ch04/ch4-04.adoc - include::example$Chapter04/2.php[]

让我们逐一查看这些代码块，以了解这里发生了什么。如果我们从头开始看，就会发现在构造方法中，我们创建了一个新的 LinkedList 对象，并将其赋值给堆栈属性，而不是上一个示例中的数组。我们假设 LinkedList 类是自动加载的，或者脚本中包含了该文件。现在，让我们把重点放在推送操作上。推送操作非常简单。我们只需要在链接列表中插入一个新节点。由于我们对链表的大小没有限制，因此不会检查任何溢出。

在我们的链表实现中，没有显示最后一个节点的方法。我们插入了一个新的最后一个节点，并删除了之前的最后一个节点，但在这里，我们需要在不删除最后一个节点的情况下获取其值。为了实现这一功能，也就是我们堆栈的顶部操作，我们可以利用关联列表实现中的 getNthNode 方法和 getSize 方法。这样，我们就能获得节点。但我们必须记住一点：我们要的是节点的字符串值，而不是完整的节点对象。这就是为什么我们要返回返回节点的 data 属性。

与 top 操作类似，pop 操作也需要在从列表中删除最后一个节点之前返回它的数据。为此，我们使用了 top() 方法和 LinkedList 类中的 deleteLast() 方法。现在，让我们运行一段示例代码，使用这个新实现的 BookList 类进行堆栈操作。代码如下：

Unresolved include directive in modules/ROOT/pages/ch04/ch4-04.adoc - include::example$Chapter04/2.php[]

它看起来与我们运行的上一个示例十分相似，但在这里，我们要执行两次弹出操作，然后再执行最上面的操作。因此输出结果如下：

MySQL Workbench tutorial
Mastering JavaScript
Introduction to PHP7

如果我们知道堆栈的基本行为以及实现堆栈的方法，我们就可以使用数组、链表或双链表来实现堆栈。由于我们已经了解了数组和链表的实现方法，现在我们将探讨堆栈的 SPL 实现方法，它实际上使用的是双链表。