队列实现栈&栈实现队列
前言
给你两个栈你如何实现一个队列，给你两个队列你如何实现一个栈。
本文就跟大家分享下这两个问题的解决思路与实现过程，欢迎各位感兴趣的开发者阅读本文。
问题分析
我们先来看下栈与队列的特性：
- 栈：最先加入的元素最后出
- 队列：最先加入的元素最先出
有关栈与队列的详细讲解请移步我的另一篇文章：数据结构:栈与队列
有了栈与队列的理论基础后，我们就可以利用其特性来分析问题了，我们先来看下如何用栈来实现队列：
- 我们的已知条件只有两个栈，将这两个栈进行标识：栈1、栈2
- 执行入队操作时，我们元素放进栈1。
- 执行出队操作时：
- 把栈1的元素压入栈2
- 栈2顶部元素出栈
上述思路中，我们用栈1来存储元素，我们知道栈的规则是先进后出，因此我们将栈1的元素压入栈2后，将栈2元素出栈时，刚好符合队列的特性。
接下来，我们来看下如何用队列来实现栈：
- 同样的，我们的已知条件有两个队列，将这两个队列进行标识：队列1，队列2
- 执行入栈操作时，将元素放进队列1
- 执行出栈操作时：
- 如果队列2为空，我们将队列1中除队首外的元素放进队列2
- 如果队列2不为空，我们将队列2的元素放进队列1
- 队列1元素出队
上述思路中，我们将元素都放入了队列1，出栈时，我们只保留队列1的队首元素，其他元素全部放入了队列2，随后将队列2的元素又放回了队列1，最后将队列1的元素出队，经过我们的这番倒腾后，刚好符合了栈的特性。
实现代码
经过上述分析，我们有了实现思路，接下来我们就将上述思路转化为具体的代码，下述代码中将引入我们之前写好的队列与栈的实现代码，对此不了解的开发者请移步我的另外两篇文章：数组实现栈与对象实现栈、队列与双端队列的实现
栈实现队列
- 创建StacksAndQueues类文件，声明解决本文问题所需要的变量
// 栈与队列的相关操作
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());
代码地址
本文实现代码的完整地址如下：
- StacksAndQueues.ts
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-03-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录