数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学如何仅使用两个栈在 JavaScript 中实现入队和出队？
在本教程中，我们将仅使用两个栈来实现队列。这是一个非常常见的面试问题，所以知道如何做是很好的。
算法
步骤 1 - 我们有两个栈，一个用于入队，一个用于出队。
步骤 2 - 我们通过推入入队栈来入队。
步骤 3 - 我们通过弹出出队栈来出队。
步骤 4 - 如果出队栈为空，我们弹出入队栈中的所有元素并将其推入出队栈。
步骤 5 - 这会反转顺序，以便最旧的项目现在位于出队栈的顶部。
实现
现在让我们看看这如何在代码中工作。我们将创建一个具有两个方法（入队和出队）的 Queue 类。
class Queue { constructor() { this.enqueueStack = []; this.dequeueStack = []; } enqueue(item) { this.enqueueStack.push(item); } dequeue() { if (this.dequeueStack.length === 0) { // move everything from enqueueStack to dequeueStack while (this.enqueueStack.length > 0) { const item = this.enqueueStack.pop(); this.dequeueStack.push(item); } } // dequeue from dequeueStack return this.dequeueStack.pop(); } }
在上面的代码中，我们有一个 Queue 类，它有两个方法，enqueue 和 dequeue。
我们通过推入 enqueueStack 来入队。
我们通过弹出 dequeueStack 来出队。如果 dequeueStack 为空，我们将从 enqueueStack 弹出所有内容并将其推入 dequeueStack。这会反转顺序，以便最旧的项目现在位于 dequeueStack 的顶部。
示例
以下是使用仅两个栈实现入队和出队的完整可运行代码。
<!doctype html> <html> <body> <h3> Implementing enqueue and dequeue using two stacks </h3> <div id="result1"></div> <div id="result2"></div> <div id="result3"></div> <script> class Queue { constructor() { this.enqueueStack = []; this.dequeueStack = []; } enqueue(item) { this.enqueueStack.push(item); } dequeue() { if (this.dequeueStack.length === 0) { // move everything from enqueueStack to dequeueStack while (this.enqueueStack.length > 0) { const item = this.enqueueStack.pop(); this.dequeueStack.push(item); } } // dequeue from dequeueStack return this.dequeueStack.pop(); } } // testing const queue = new Queue(); // enqueue three strings queue.enqueue("tutorials"); queue.enqueue("point"); queue.enqueue("JavaScript"); document.getElementById("result1").innerHTML = queue.dequeue(); // 1 document.getElementById("result2").innerHTML = queue.dequeue(); // 2 document.getElementById("result3").innerHTML = queue.dequeue(); // 3 </script> </body> </html>
使用两个栈的一个好处是我们可以保持入队栈排序。这样，当我们将所有内容从入队栈移动到出队栈时，项目将已经按正确的顺序排列。
使用两个栈有一些缺点。
首先，它比使用单个栈实现的队列占用更多内存。
其次，它效率较低。每个入队和出队操作都需要两个栈操作（推入和弹出）。
在本教程中，我们已经了解了如何仅使用两个栈来实现队列。这是一个非常常见的面试问题，所以知道如何做是很好的。
更新于：2022年8月3日
1K+ 次查看
广告