使用堆栈实现队列
来源: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学习网公众号!
-
501 收藏
-
501 收藏
-
501 收藏
-
501 收藏
-
501 收藏
-
369 收藏
-
106 收藏
-
232 收藏
-
239 收藏
-
446 收藏
-
268 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 立即学习 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 立即学习 507次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 立即学习 497次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 立即学习 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 立即学习 484次学习