使用堆栈实现队列

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

在整篇文章中，我将使用 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。

我们的输入有点像这样：

完整的主要功能是：

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

以上就是使用堆栈实现队列的详细内容，更多请关注硕下网其它相关文章！