Tag: 链表

反向链接列表: 我目前正在解决iOS开发人员遇到的常见数据结构/算法问题，并且反向链接列表就是其中之一。我们需要做的第一件事是建立链接列表的基础。因此，我们要做的是编译将成为列表的节点列表，oneNode，twoNode和ThreeNode。让我们编写一个函数以打印出链接列表，以仔细检查所有文件的顺序是否正确。查看打印输出。为了真正理解我们应该如何反向链接列表，让我们使用一些箭头来指示每个节点如何相互引用以及其最终外观如何。目前，我们的链接列表如下所示： 1→2→3→无我们想要的是……。 3→2→1→无反转列表的方式应如下所示：无←1→2→3→无无←1←2→3→无无←1←2←3 我们要完成的工作与反转数组有很大不同，在这种情况下，您可以简单地从最后一个元素开始迭代，然后从第一个元素结束。这是实际上反转指针并确保正确调整头和尾以及其所有下一个值的问题。让我们看一下这里发生的事情。我们将currentNode设置为等于头，即链表中的第一个节点。 currentNode还是在while循环中用于定义条件语句的变量。接下来，我们还有两个变量，previousNode和nextNode，它们也将进行更改。只要currentNode不等于nil，我们就想遍历列表，如果它变为nil，我们想跳出循环。 1→2→3→n的可视化在这里很有用。因此，我们要做的第一件事就是将nextNode设置为等于currentNode的下一个节点。因此，我们从列表开始，以1为头节点，然后将nextNode设置为2，因此nextNode = currentNode？.next。然后，我切换了齿轮以在return语句之前编写最后一行代码，即currentNode = nextNode，因为对我而言，从逻辑上讲，当我们完成对所有其他变量的引用的更改后，我们需要一个新的头节点迭代并重新计算所有其他值。现在是棘手的部分……我们该如何处理previousNode和currentNode的next属性？在我们的循环中，到目前为止，previousNode的值是以下nil，1、2。如果要递增，我们希望这些值变为1、2、3或previousNode等于CurrentNode。但是，我们仍然需要容纳currentNode？.next，它在更改它之前指向了previousNode。本质上，我们在翻转currentNode？.next和previousNode的值，如果我们注释掉这一行，则您会注意到节点列表未打印，它的位置是3。currentNode？.next = previousNode有助于跟踪之前的哪个节点在thirdNode之前。然后，当我们考虑外循环的下一个迭代时，我们将previousNode设置为currentNode，因为它是列表中的下一个节点。最后，将currentNode更改为nextNode，以继续到下一个节点值。您返回上一个节点是因为我们要返回链接列表中的新“头”或初始节点。

堆栈和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行） […]