登录
首页 >  文章 >  python教程

使用堆栈实现队列

来源:dev.to

时间:2024-11-28 21:10:06 153浏览 收藏

golang学习网今天将给大家带来《使用堆栈实现队列》,感兴趣的朋友请继续看下去吧!以下内容将会涉及到等等知识点,如果你是正在学习文章或者已经是大佬级别了,都非常欢迎也希望大家都能给我建议评论哈~希望能帮助到大家!

队列和堆栈是我们在日常编码中使用的相当简单的数据结构。事实上,它们可以被认为是维护数据最简单的结构。

在整篇文章中,我将使用 DS 来指代数据结构。

Queue是一个按照先进先出原则工作的DS。先来的数据被允许先出去。实现队列的方法有很多种。我们可以自由地使用数组、链表等。但在这里,我将讨论使用另一个称为 Stack 的 DS 来实现 Queue。

现在,我们都知道,Stack 是一个按照 LIFO 原理工作的 DS。我总是考虑把书一本一本地堆放在另一本上面,所以如果它可以帮助你想象的话,请随意使用这个类比。

我在 hackerrank 中遇到了这个问题,他们要求我们使用 2 个堆栈来实现队列。听起来很简单吧?花点时间思考一下我们如何才能实现这一目标。

您可能已经想出了一些解决方案,因为有很多方法可以做到这一点。那你为什么不直接尝试一下呢?

问题

现在,对于那些尝试过但遇到“超时错误”的人和那些懒得尝试的人,让我向您解释解决此问题的最简单、最容易的方法。

首先看一下stack是如何实现的。

使用堆栈实现队列

如你所见,我使用列表实现了堆栈。最初,构造函数初始化一个空列表。我们通过将数据附加到列表末尾来推送数据。弹出时,如果我们不提供索引,它将从列表末尾弹出。因此,最后插入的元素是第一个弹出的。

现在,以与队列类似的方式,我们已经初始化了两个不同的堆栈。一种用于入队,一种用于出队。

我们使用类似于堆栈的enqueueStack,只是将数据推送到列表末尾。但是对于 dequeueStack,我们知道堆栈的 pop 函数会从最后一个元素中删除元素,所以我们要做的是;我们反转enqueueStack并将其放入dequeueStack中。因此,enqueueStack的第一个元素成为dequeueStack的最后一个元素,enqueueStack的第二个元素成为dequeueStack的倒数第二个元素,依此类推。所以现在如果我们对 dequeueStack 使用 pop 函数,那么它将删除我们推送的第一个元素,从而模仿队列。

如果现在这听起来令人困惑,请不要担心!一旦你看到代码,你就会明白我在说什么。事实上现在就看看吧!

使用堆栈实现队列

您可能想知道这些额外检查的用途是什么。就像检查 dequeueStack 是否为空一样。如果我们最初不检查它。通过反转,enqueueStack 的元素将进入 dequeueStack,发生的情况是原本应该位于第一个的出队 Stacks 元素现在最终成为最后一个。因此,首先必须清空 dequeueStack,如代码所示。

与此类似,printFront 打印应该位于队列前面的项目。

在此实现之后,我们从 STDIN 读取输入并将输出打印到 STDOUT。

我们的输入有点像这样:

使用堆栈实现队列

完整的主要功能是:

使用堆栈实现队列

我尝试以尽可能简单的方式实现这一点。可能还有其他几种更好的方法来实现这一点。这里展示其中之一!

以上就是《使用堆栈实现队列》的详细内容,更多关于的资料请关注golang学习网公众号!

声明:本文转载于:dev.to 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>