Tag: 堆栈

堆栈和LIFO结构：实现和用例: 很少有数据结构像堆栈那样普遍存在。它们易于理解和实现，但它们的强大之处在于强大。本文的目的是解释什么是堆栈以及如何实现堆栈，并介绍三个实际用例。让我们开始吧！在此处克隆本文随附的存储库。说明：堆栈与数组堆栈是一种结构，负责遵循LIFO原理（后进先出）动态地收集数据。打个比方，您可以想象一堆自助餐厅托盘：当您要添加一个新托盘时，它将被引入到堆叠顶部（而不是插入其中）。由于最后一个纸盘在纸堆的顶部，因此当需要一个单独的纸盘时，它也将是第一个脱落的纸盘。堆栈提供两个主要功能：“推动”或引入一个新元素，以及“弹出”或除去最后一个元素。如果我们将此结构与典型数组进行比较，就会发现一些明显的区别。尽管Swift会以智能方式处理数组的内存分配，但在基础语言中，数组容量是在初始化期间设置的，并且是静态的。另一方面，堆栈根据需要为单个节点分配和取消分配内存，这使它们非常灵活。此外，数组允许访问任何索引的元素，而堆栈仅与终端节点进行交互。尽管这似乎很有限（确实是……），但它实际上使数据访问非常轻巧且快速。此外，LIFO行为对于解决特定情况可能非常有用，我们将在本文后面介绍。堆栈：演示实现有几种方法可以实现堆栈，但是在本演示中，我们将创建一个双向链接列表，该列表清楚地演示了在引入新元素时的动态内存分配。首先，让我们仅查看所需的类和属性：接下来，让我们看一下如何将新元素压入堆栈。步骤1：使用所需的值创建一个新节点。步骤2：假设endNode指向一个节点，我们可以将端节点中的下一个属性分配给新节点，并将新节点中的前一个属性分配回端节点。请记住，先前的属性很弱，因此我们避免了保留周期。步骤3：最后，我们可以通过访问endNode的next属性将其endNode指针移至newNode。请注意，列表所需的内存随着newNode的分配和初始化而增长。我们的pop（）方法删除端节点并返回该节点中的值。步骤1：我们将值存储在端节点的临时常量val中。步骤2：我们通过使用endNode指针的先前属性将其向后移动一个元素。步骤3：我们将endNodes的next属性设置为nil。现在，最后两个节点之间的唯一参考是通过标记为弱的先前属性。这意味着从内存中释放了该节点。步骤4：我们返回最后一个节点中的值。在解释了这些重要方法之后，让我们看一下Stack类的最终实现： push和pop方法的出现与我们期望的完全一样（第13–32行）。我们可以使用push方法创建带有一些可变参数值的自定义初始化程序（第7-11行）。另外，我们可以通过检查rootNode是否具有值（第34–36行）并具有基本的打印方法（只要它能够通过下一个属性访问节点）来遍历列表（第38–36行），以检查堆栈是否为空。 44）。我们的堆栈功能的基本测试如下所示：知道如何实现堆栈是一回事，但更重要的是识别适合堆栈的情况。在下一部分中，我们将研究三种此类情况。用例1：冲销订单因为堆栈的顺序是固定的，所以通过将元素从一个堆栈弹出并立即放在另一个堆栈上可以非常容易地实现逆序。不用乱搞索引！用例2：测试对称性堆栈的另一个好用例是测试对称性。在下面的示例中，我们正在测试一串括号，以确保每个闭合括号与先前的打开括号正确匹配。我们首先检查字符数是否可以被不整数（第6行）立即除以2的奇数个字符。接下来，我们通过定义一个非法字符字符集来检查我们是否具有有效的输入，然后检查我们的输入字符串是否包含零个非法字符范围（第7-8行） […]

堆栈: 在舒适地使用了数据结构数组和字典之后，我将探索诸如Stacks和Queues之类的不熟悉的数组。在本文中，我们将重点介绍Stacks。排队等待我有关队列的文章。堆叠—遵循后进先出（LIFO）的顺序。 1. PUSH —只能将元素推到堆栈的顶部 2. POP —从堆栈顶部删除元素 3. PEEK-窥探堆栈顶部的元素将一堆书想象成一堆书，但要用书本的内容代替书而不是书（而不是心脏……哈）。在生活中，您不想遇到任何泛型，但是在为Stack编写代码时，我已经使用泛型实现了进一步的可重用性。让我们大致了解一下实际发生的情况。我们有一个变量数组，仅对我们正在使用的文件具有有限的访问权限。在该数组中，每当我们添加一个元素时，该元素都会作为最后一个元素添加，如果您尝试删除元素，则最后一个添加的元素也会被删除。最后，您只能看到堆栈中的最后一个元素。这是Stacks的一个更有趣的版本。我创建了一个名为Lannister的结构，然后继续创建三个相同类型的对象Lannister。然后，我将这些元素放入Lannister堆栈中，并能够获得对我已推送的所有内容的描述。