后端开发教程 - Java、Spring Boot 实战 - msg200.com
JavaScript 中的堆栈与队列
堆栈
队列
队列和堆栈是技术面试中常见的两种数据结构。由于它们的结构非常相似，区分起来可能有点困难。所以今天我们将用 JavaScript 构建一个堆栈和一个队列。
堆栈
堆栈是一种遵循“后进先出”或“LIFO”范式的数据结构。我们可以把它们想象成一摞书。为了取出第三本书，我们必须先取出第五本书，然后再取出第四本书，直到取出第三本书。
JavaScript 不提供本机堆栈数据结构，因此我们必须使用数组和闭包或类来构建自己的数据结构。
好处
堆栈允许以常数时间添加和移除元素。这是因为我们不需要移动元素来添加和移除堆栈中的元素。
约束
不幸的是，与数组不同，堆栈不能提供对堆栈中第 n 个元素的恒定时间访问。这意味着它可能需要 O(n) 的时间复杂度（其中 n 是堆栈中元素的数量），才能检索到该元素。
方法
堆栈利用以下方法：
pop()：从堆栈中移除顶部元素push(item)：将项目添加到堆栈顶部peek()：返回堆栈顶部的项目isEmpty()：如果堆栈为空，则返回 true
让我们一起构建
让我们创建一个 BookStack 对象，用来存放我们最喜欢的小说。堆栈的优点在于，它的 push 和 pop 方法与我们将要使用的数组方法同名。
构造函数
我们将定义一个 BookStack 类并赋予它一个具有一个属性的构造函数方法：
this.stack = [];
constructor() {
this.stack = [];
}
得到
我将添加一个 getter 来返回堆栈的长度。我们将在其他方法中使用它。
get length() {
return this.stack.length;
}
推
我们想将元素添加到数组的末尾，因此可以使用该array.push()方法。该array.push()方法返回新的长度数组。
push(item) {
return this.stack.push(item);
}
流行音乐
我们想要删除数组中的最后一项，因此可以使用该array.pop()方法。该array.pop()方法返回新添加的项，如果数组现在为空，则返回 undefined。
pop() {
return this.stack.pop();
}
窥视
我们想要返回（或者说查看）堆栈中的最后一个元素。因此，我们只需要访问最后一个索引处的值。
peek() {
return this.stack[this.length - 1];
}
为空
如果堆栈中没有元素，我们希望返回 true。因此，如果长度为零，则返回 true。
isEmpty() {
return this.length === 0;
}
整合起来
我们的最终 BookStack 代码如下所示：
class BookStack {
constructor() {
this.stack = [];
}
push(item) {
return this.stack.push(item);
}
pop() {
return this.stack.pop();
}
peek() {
return this.stack[this.length - 1];
}
get length() {
return this.stack.length;
}
isEmpty() {
return this.length === 0;
}
}
您还可以使用闭包来创建它。
function BookStack() {
const stack = [];
return {
push(item) {
return stack.push(item);
},
pop() {
return stack.pop();
},
peek() {
return stack[this.length - 1];
},
get length() {
return stack.length;
},
isEmpty() {
return this.length === 0;
}
}
}
让我们用一些书籍数据来测试一下。
let myBookStack = new BookStack();
myBookStack.push('Oathbringer');
myBookStack.push('The Stand');
console.log(myBookStack.length); // 2
console.log(myBookStack.peek()); // The Stand
myBookStack.pop();
console.log(myBookStack.length); // 1
console.log(myBookStack.peek()); // Oathbringer
console.log(myBookStack.isEmpty()); // false
myBookStack.pop();
console.log(myBookStack.isEmpty()); // true
您可以在此处查看 CodePen 。
队列
队列在结构和方法上与栈类似，但范式不同。队列采用“先进先出”或“FIFO”方法。这可以想象成人们排队等待购买电影票的样子。
排队时间最长的人比刚加入的人先得到服务。
用例
队列与链表非常相似，通常用于广度优先搜索或实现缓存。
约束
添加和删除节点时，队列的更新变得更加困难。
方法
队列利用以下方法：
enqueue(item)：从队列中删除顶部项目dequeue()：将项目添加到队列顶部peek()：返回队列顶部的项目isEmpty()：如果队列为空，则返回 true
让我们一起构建
本例中我们将使用 JavaScript 类。如果您想了解函数闭包的具体操作，请参阅堆栈部分。
构造函数
我们将定义一个 MovieQueue 类并赋予它一个具有一个属性的构造方法：
this.queue = [];
constructor() {
this.queue = [];
}
得到
我将添加一个 getter 来返回队列的长度。我们将在其他方法中使用它。
get length() {
return this.queue.length;
}
入队
我们希望将一个项目添加到数组的第一个索引（队列的末尾）。因此，让我们使用该array.unshift()方法。
enqueue(item) {
return queue.unshift(item);
}
出队
我们想要删除队列中的第一个元素，或者数组中的最后一个元素。我们可以简单地使用该array.pop()方法来实现。
dequeue() {
return queue.pop();
}
窥视
我们想看看队列中的第一个元素是什么。记住，这是数组中的最后一个元素。我们将用它queue[this.length — 1]来获取这个值。
peek() {
return queue[this.length - 1];
}
为空
如果队列为空，我们希望返回 true。我们可以使用 length 方法来获取此信息。
isEmpty() {
return this.length === 0;
}
整合起来
我们的最终 MovieQueue 代码如下所示：
class MovieQueue {
constructor() {
this.queue = [];
}
enqueue(item) {
return this.queue.unshift(item);
}
dequeue() {
return this.queue.pop();
}
peek() {
return this.queue[this.length - 1];
}
get length() {
return this.queue.length;
}
isEmpty() {
return this.queue.length === 0;
}
}
让我们用一些名字来测试一下。
const myMovieQueue = new MovieQueue();
myMovieQueue.enqueue('Sandra');
myMovieQueue.enqueue('Rob');
myMovieQueue.enqueue('Lisa');
myMovieQueue.enqueue('Kai');
console.log(myMovieQueue.length); // 4
console.log(myMovieQueue.peek()); // Sandra
myMovieQueue.dequeue();
myMovieQueue.dequeue();
console.log(myMovieQueue.peek()); // Lisa
您可以在此处查看 CodePen 。
我希望本教程能让您更好地了解队列和堆栈之间的区别！
文章来源：https://dev.to/emmabostian/stacks-vs-queues-in-javascript-4d1o