Tag: 数据结构

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

使用Swift实现基于堆的优先级队列: 在计算机科学中存在很多问题，其中使用优先级队列作为基础数据结构可以极大地提高算法的时间复杂度。 Dijkstra的最短路径算法就是一个例子，该算法使用优先级队列在图形中搜索两个顶点之间的最短路径。遗憾的是，Swifts标准库没有默认的优先级队列实现，因此我们将研究如何自行实现基于堆的优先级队列。要继续使用自己的IDE，请单击此链接以获取源代码！什么是优先队列？优先级队列是一种数据结构，可以对具有相对优先级的对象进行有效的排序。您可以将一堆对象放入队列，然后根据它们之间相互比较的重要性将它们一一递回。假设您已经为计算机创建了许多任务，以便它们在将来的某个特定时间运行。将它们添加到优先级队列将使您的计算机使任务出队，并在仍在等待其截止日期的任务之前获得应执行的对象。为了实现我们的队列，我们将使用堆结构！什么是堆？可以将堆看作一棵树，其中每个节点最多有2个子节点。堆还具有以下限制：它需要将所有新节点添加到顶层，并尽可能地添加到最左边。看一下下面的图片：堆还维护与每个节点的相对大小有关的属性。最小堆（这是我们将要使用的堆）保持以下属性：每个节点都小于其两个子节点，而最大堆则相反。为了能够维护此属性，我们将需要进行一些操作以获得正确的节点顺序。当我们插入一个新节点时，我们将其添加到树顶部左侧的第一个可用位置。如果完成此操作后min min属性不成立，我们将开始与该节点的父节点交换节点，直到达到再次拥有min堆的状态。下图显示了将2插入到现有的最小堆中时发生的情况：

Swift数据结构：堆栈: 堆栈是一个简单的数据结构，可让您创建项目的线性“堆栈”（因此得名）。它是一种LIFO（“后进先出”）数据结构，这意味着添加到堆栈中的最后一个项目是可以删除的第一个项目。它有一些非常实用的用例，如果您今天在计算机上做过任何事情，那么您已经与Stack进行了交互。您将了解当前在何处使用Stack以及如何使用它。对于您的视觉学习者，这是一个图表。堆栈显示有6个项目。如您所见，我为每个项目赋予了绿色索引。尽管在与Stack本身进行交互时并不会真正使用它，但它使我们能够依赖于已内置的数据类型Array来帮助我们组织Stack。堆栈中的值没有按照任何特定的方式进行组织，除了以下事实：添加新项目时，所有当前值都向下移动一个索引，然后将新的索引添加到堆栈的顶部，就像这样做一样与一叠饭菜。堆栈具有3个可以与之交互的函数。我们将在下面简要讨论每个对象及其作用：函数1：peek（）我们的第一个函数称为peek() ，它使您可以做到这一点–窥视堆栈中最顶层的元素。它将返回该项目在顶部以供使用或仅供参考。它不会改变堆栈中的数据。函数2：pop（）顾名思义， pop()从堆栈中返回顶层项目，然后将其删除。如果要删除最上面的项目并允许撤消该操作，此功能特别有用。由于返回并删除了最上面的项目，请设想我们有一个应用程序，可让您输入要完成的任务。提交后，它将位于堆栈的顶部。如果您犯了一个错误或输入了错误的内容，则可以通过调用pop()并继续进行操作来删除它，也可以修改刚刚输入的内容，因为会返回该值。您可以使用返回的文本填充文本字段，对其进行修改，然后重新提交到堆栈。函数3：push（）函数push（）将允许我们向堆栈中添加值。就那么简单。由于新的值已添加到堆栈的顶部，因此它会更改堆栈中的值。现在，您知道堆栈是什么以及它如何工作（理论上），让我们继续。聊够了，让我们动手吧。 💪打开Xcode并创建一个新的Playground。删除所有样板代码并import Foundation 。然后，在该行下面创建Stack结构，并添加一个私有变量数组，称为String类型的items 。将其值设置为空数组：

堆数据结构实现— Swift 4: 动机这篇文章旨在帮助您了解堆数据结构并在Swift中实现它。在进入实现部分之前，必须先具备swift和heap知识。什么是堆堆是一种完整的二叉树的特殊类型，它的父节点与其子节点进行比较，从而为您提供数据结构中的最大值或最小值。通常有两种类型。最大堆：在最大堆中，父节点将始终大于其子节点。所有其他节点可以按任何顺序排列最小堆：在最小堆中，父节点将始终小于其子节点。所有其他节点可以按任何顺序排列。注意：当您只关心最小值或最大值时，堆数据结构很有用。所有其他值将是无序且无排序的。优先级队列是可以使用堆数据结构的典型示例。实作现在，我们将实现具有所有功能的最小堆。实现需要执行以下步骤： 1.向堆添加值 2.从堆中删除最少的元素 3.从堆中获取最少的元素我们开工吧。创建堆类堆可以用数组表示。一个父节点可以有一个左子节点和一个右子节点。我们可以通过以下方式获取正确的Child的索引和离开的孩子的索引左儿童索引= 2 *父索引+1 右子索引= 2 *父索引+2 用同样的方式 ParentIndex =（childIndex-1）/ 2 在堆类中实现所需的方法将这些方法添加到堆类中。现在，我们将添加在Heap上执行自定义操作的方法。添加这些方法 peek（）返回堆中的最小元素 poll（）与peek一样，但是它也删除了最小元素 add（）将元素添加到堆中 removeMin（）删除堆中的最小元素现在您一定在想，什么是heapifyDown（）和heapifyUp（）让我们实现它们堆砌这是在将元素添加到列表之后发生的过程。因此，如果要在堆中添加元素，只需将其添加到最后一个元素，然后开始与父元素进行比较，直到堆满足条件为止 HeapifyDown 当您删除列表中的最小元素并且堆必须重新排列自身以满足条件时，就会发生此过程。对于父节点，它将检查子节点是否小于父节点（如果是），然后交换该值。它一直持续到堆满足其先决条件为止。让我们添加printMethod来打印堆让我们使用这些方法来处理堆。 […]

数据结构: 堆栈和队列堆堆栈是后进先出数据结构。想象一下一大堆砖头。您已经承担了将这些砖块放在盒子中运输的任务。那么，看看这个庞大的堆栈，我们是从堆栈的底部开始拉砖还是从顶部取砖？常识将指示我们从顶部开始，而不是从10,000磅的Jenga游戏开始。这很像堆栈在这里的工作方式。放置在LIFO数据结构中的最后一个元素是从中检索的第一个元素。尽管堆栈可能从表面上看起来像数组，但元素的顺序支撑了功能。因此，在创建堆栈时，必须限制访问堆栈中元素的方式。队列队列是先进先出列表数据结构。先进先出数据结构意味着元素只能在后面插入，并在前面出队。队列在现实世界中最好用购买电影票的线来表示。在售票热线中，第一个排队的人首先要购买门票，排队的每个人都按照加入队伍的顺序购买门票。像使用Stacks一样，从队列中删除数据的顺序对于其能否正常运行至关重要，因此确保对队列数据的访问进行适当管理至关重要。 var queue = Queue （） queue.isEmpty // true queue.push（值：“一个”） print（queue.count） // 1 queue.push（值：“两个”） print（queue.count） // 2 queue.push（值：“三”） print（queue.count） // 3 queue.push（值：“四个”） print（queue.count） // 4 queue.isEmpty // 否 print（queue.pop（）） //一个 print（queue.pop（）） //两个 print（queue.pop（）） //三个 print（queue.pop（）） //四个堆栈和队列的实际使用在需要保留列表顺序或添加或删除项的顺序很重要的情况下，堆栈和队列可用作临时数据结构。