本文转载自微信公众号「神奇的程序员K」,作者神奇的程序员K。转载本文请联系神奇的程序员K公众号。
前言
给你两个栈你如何实现一个队列,给你两个队列你如何实现一个栈。
本文就跟大家分享下这两个问题的解决思路与实现过程,欢迎各位感兴趣的开发者阅读本文。
问题分析
我们先来看下栈与队列的特性:
有关栈与队列的详细讲解请移步我的另一篇文章:数据结构:栈与队列
有了栈与队列的理论基础后,我们就可以利用其特性来分析问题了,我们先来看下如何用栈来实现队列:
上述思路中,我们用栈1来存储元素,我们知道栈的规则是先进后出,因此我们将栈1的元素压入栈2后,将栈2元素出栈时,刚好符合队列的特性。
接下来,我们来看下如何用队列来实现栈:
上述思路中,我们将元素都放入了队列1,出栈时,我们只保留队列1的队首元素,其他元素全部放入了队列2,随后将队列2的元素又放回了队列1,最后将队列1的元素出队,经过我们的这番倒腾后,刚好符合了栈的特性。
实现代码
经过上述分析,我们有了实现思路,接下来我们就将上述思路转化为具体的代码,下述代码中将引入我们之前写好的队列与栈的实现代码,对此不了解的开发者请移步我的另外两篇文章:数组实现栈与对象实现栈、队列与双端队列的实现
栈实现队列
- // 栈与队列的相关操作
- import Stack from "../../StackTest/lib/Stack.ts";
- import Queue from "../../QueueTest/lib/Queue.ts";
- export default class StacksAndQueues {
- private firstStacks: Stack;
- private secondStacks: Stack;
- private firstQueues: Queue;
- private secondQueues: Queue;
- constructor() {
- this.firstStacks = new Stack();
- this.secondStacks = new Stack();
- this.firstQueues = new Queue();
- this.secondQueues = new Queue();
- }
- }
- // 入队
- enqueue(key: string | number): void {
- // 入栈1
- this.firstStacks.push(key);
- }
- // 出队
- dequeue() {
- while (!this.firstStacks.isEmpty()) {
- this.secondStacks.push(this.firstStacks.pop());
- }
- if (!this.secondStacks.isEmpty()) {
- // 出栈2
- return this.secondStacks.pop();
- }
- return null;
- }
接下来,我们通过一个例子来验证下上述代码能否正常执行:
- import StacksAndQueues from "./lib/StacksAndQueues.ts";
- // 用栈实现队列
- const stacksAndQueues = new StacksAndQueues();
- stacksAndQueues.enqueue(3);
- stacksAndQueues.enqueue(9);
- stacksAndQueues.enqueue(12);
- console.log("出队", stacksAndQueues.dequeue());
- console.log("出队", stacksAndQueues.dequeue());
- console.log("出队", stacksAndQueues.dequeue());
队列实现栈
- // 入栈
- stackPush(key: string | number) {
- // 入队1
- this.firstQueues.enqueue(key);
- }
- // 出栈
- stackPop() {
- if (this.firstQueues.isEmpty()) {
- return null;
- }
- // 队列2为空
- if (this.secondQueues.isEmpty()) {
- while (this.firstQueues.size() != 1) {
- // 将队列1除队首外的元素放进队列2
- this.secondQueues.enqueue(this.firstQueues.dequeue());
- }
- }
- // 队列2不为空
- while (!this.secondQueues.isEmpty()) {
- // 将队列2的元素放进队列1
- this.firstQueues.enqueue(this.secondQueues.dequeue());
- }
- // 队列1出队
- return this.firstQueues.dequeue();
- }
- // 队列实现栈
- stacksAndQueues.stackPush(3);
- stacksAndQueues.stackPush(9);
- stacksAndQueues.stackPush(12);
- console.log("出栈", stacksAndQueues.stackPop());
- console.log("出栈", stacksAndQueues.stackPop());
- console.log("出栈", stacksAndQueues.stackPop());
代码地址
本文实现代码的完整地址如下:
TOP云 (west.cn)1月25日消息,近日,功夫贷宣布获得4000万人民币A轮融资,本轮...
我们知道效能提升 就是要应用系统方法实践和工具 通过它们改进技术、工程能力和...
背景 2020年9月16日 Snowflake成功IPO 交易首日市场估值达到704亿美元 募集资金3...
约束与限制 只有运行中的云服务器云主机才允许用户登录。 Windows操作系统用户名...
作者 | 亮言 来源 | 阿里技术公众号 一 背景 订单状态流转是交易系统的最为核心...
本文介绍了北京慧达天下如何使用运维编排OOS提高发布效率。 公司介绍 公司名称:...
本文由网易云音乐实时计算平台研发工程师岳猛分享,主要从以下四个部分将为大家...
有很多人在听说大数据之后,会开始纠结JAVA与大数据的区别,甚至还在纠结Java和...
描述 你正在和你的朋友玩 猜数字 (Bulls and Cows)游戏:你写下一个数字让你的朋...
hk 域名 哪里注册? .hk域名 在国内是可以注册的,只要提供了.hk 域名注册 服务...