如何在JavaScript中实现栈(Stack)和队列(Queue)？
我想要使用逆波兰表达式算法，因此需要这些数据结构。
32个回答
1677
var stack = [];
stack.push(2); // stack is now [2]
stack.push(5); // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i); // displays 5
var queue = [];
queue.push(2); // queue is now [2]
queue.push(5); // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i); // displays 2
来源于 "9个你可能不知道的JavaScript小技巧"
- Corey Ballou
12
314我建议使用queue.shift时要小心。据我所知，它的时间复杂度不是O(1)，而是O(n)，如果队列变得很大，可能会太慢。 - MAK
25我认为这取决于JavaScript的实现。我不认为它在JavaScript规范中有明确定义。 - Georg Schölly
1@MAK/gs: 队列是密集的，因此大多数JS实现应该将值存储在实际的动态大小数组中（Java称之为
ArrayList）；这意味着移位很可能涉及到memmove()；不过你需要检查你选择的JS引擎的源代码来确保。 - Christoph2Array.join() 在 JS 中现在比通常的 '+' 运算符慢，这是因为 Array.join() 没有像 '+' 运算符一样接收到许多优化更新... 在使用它们之前，我建议您仔细研究所有这些提示。 - anpatel
1ImmutableJs是一种非常适合所有不可变数据的库，包括栈。而且，它的效率是O(1)。https://facebook.github.io/immutable-js/docs/#/Stack - Lukas Liesis
显示剩余7条评论
97
数组。
栈：
var stack = [];
//put value on top of stack
stack.push(1);
//remove value from top of stack
var value = stack.pop();
队列：
var queue = [];
//put value on end of queue
queue.push(1);
//Take first value from queue
var value = queue.shift();
- Jani Hartikainen
8
1Array.prototype.pop 不会移除数组顶部（第一个元素）的值。
它会移除数组底部（最后一个元素）的值。 - Michael Geller
38@MichaelGeller 数组的顶部是数组的最后一个元素。数组的push和pop方法的行为就像一个栈。 - mrdommyg
@mrdommyg Array.prototype.pop会移除数组的最后一个元素（请参见https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/pop）。在这里，“最后”指的是具有最高索引的元素。在JS中，数组与堆栈无关。它不是堆栈，仅仅因为它有一个pop方法。Pop只是意味着“删除最后一个元素并返回它”。当然，您可以使用数组模拟堆栈的功能，但是按照定义，数组仍然不是堆栈。它仍然是一个列表（根据MDN的说法是“类似于列表”的对象）。 - Michael Geller
12@MichaelGeller，栈的行为是“先进后出”。如果你使用JavaScript中的数组和其
push和pop方法来实现它，问题就解决了。我不太明白你的观点。 - Rax Weber3@MichaelGeller “Stack” 是一个概念。由于实现了“堆栈”的语义，JS 数组根据定义也是“堆栈”之一。即使它还实现了数组语义，这也不会改变这一点。您可以直接使用 JS 数组作为“堆栈”，在这种情况下，您推入和弹出的内容就是“顶部”元素。 - Hans
显示剩余3条评论
96
Javascript有push和pop方法，可以用于普通的Javascript数组对象。
对于队列，请查看这里：
http://safalra.com/web-design/javascript/queues/
可以使用数组对象的push和shift方法，或者使用unshift和pop方法，在JavaScript中实现队列。尽管这是一种简单的实现队列的方式，但对于大型队列非常低效。因为这些方法操作数组，每次调用shift和unshift方法时都会移动数组中的每个元素。
Queue.js是一个简单而高效的JavaScript队列实现，其出队函数以摊销常数时间运行。因此，对于较大的队列，它比使用数组要快得多。
- Robert Harvey
5
2你分享的链接具有检查基准结果的功能，但在使用Google Chrome 59版本测试时，我并未看到性能提升。Queue.js 的速度不稳定，但Chrome的速度相当稳定。 - Shiljo Paulson
我还使用queue.js制作了一个演示，其中dequeue函数实际上并没有从队列中删除该项，所以我想知道它是否应该是这样工作的？如果是这样，那么在出队前一个项目后，如何检索新队列？https://codepen.io/adamchenwei/pen/VxgNrX?editors=0001 - ey dee ey em
看起来 queue.js 中的 dequeue 也需要额外的内存，因为它使用 slice 克隆了数组。 - JaTo
此外，随着每个添加的元素，底层数组正在变得越来越大。尽管实现会不时地减小数组大小，但总体大小仍在增加。 - Philipp Mitterer
这个答案中的链接已经失效。 - adampasz
38
如果你想要创建自己的数据结构，你可以建立自己的：
var Stack = function(){
this.top = null;
this.size = 0;
};
var Node = function(data){
this.data = data;
this.previous = null;
};
Stack.prototype.push = function(data) {
var node = new Node(data);
node.previous = this.top;
this.top = node;
this.size += 1;
return this.top;
};
Stack.prototype.pop = function() {
temp = this.top;
this.top = this.top.previous;
this.size -= 1;
return temp;
};
并且针对队列：
var Queue = function() {
this.first = null;
this.size = 0;
};
var Node = function(data) {
this.data = data;
this.next = null;
};
Queue.prototype.enqueue = function(data) {
var node = new Node(data);
if (!this.first){
this.first = node;
} else {
n = this.first;
while (n.next) {
n = n.next;
}
n.next = node;
}
this.size += 1;
return node;
};
Queue.prototype.dequeue = function() {
temp = this.first;
this.first = this.first.next;
this.size -= 1;
return temp;
};
- user2954463
6
21为了避免需要迭代整个内容才能在末尾添加，通过 this.last=node; 存储对最后一个节点的引用。 - Perkins
21除非你有非常充分的理由，否则请勿实现任何类似于这样的队列...虽然它可能在逻辑上是正确的，但CPU不是按照人类抽象来运行的。遍历具有遍布各地的指针的数据结构将导致CPU缓存未命中，而顺序数组则非常高效。http://blog.davidecoppola.com/2014/05/cpp-benchmarks-vector-vs-list-vs-deque/CPU非常讨厌指针-它们可能是导致缓存未命中和需要从RAM访问内存的主要原因。 - Centril
1这是一个诱人的解决方案，但我没有看到创建的
Node 在弹出/出队时被删除...它们不会一直占用内存，直到浏览器崩溃吗？ - cneuro6与C++不同，JavaScript是一种具有垃圾回收机制的语言。它有一个
delete关键字，但仅用于将对象的属性标记为不存在，这与仅将属性分配为undefined是不同的。JavaScript还有一个new运算符，但只是在调用函数时将this设置为一个新的空对象。在C++中，您需要将每个new与一个delete配对，但在JavaScript中不需要，因为它有GC（垃圾回收）。要停止在JavaScript中使用内存，只需停止引用该对象，它最终将被回收。 - binki1设置最大堆栈大小来检查堆栈是否溢出也是必要的吗？ - li_
这些都是糟糕的实现，不要使用它们。栈应该只是数组push/pop的包装器，这已经是最优的了——分配自定义的
Node会更慢，而且代码量更大。至于队列，是的，原生数组的shift操作通常是O(n)，但是如果没有一个tail来实现队列，则push操作也是O(n)，完全违背了编写自己的队列的初衷。同样，只需使用数组来实现队列，直到O(n)的shift开始变得困难，然后使用带有tail属性的Node实现进行优化，如此处所示。 - ggorlen24
这是我使用链表实现栈和队列的代码：
// Linked List
function Node(data) {
this.data = data;
this.next = null;
}
// Stack implemented using LinkedList
function Stack() {
this.top = null;
}
Stack.prototype.push = function(data) {
var newNode = new Node(data);
newNode.next = this.top; //Special attention
this.top = newNode;
}
Stack.prototype.pop = function() {
if (this.top !== null) {
var topItem = this.top.data;
this.top = this.top.next;
return topItem;
}
return null;
}
Stack.prototype.print = function() {
var curr = this.top;
while (curr) {
console.log(curr.data);
curr = curr.next;
}
}
// var stack = new Stack();
// stack.push(3);
// stack.push(5);
// stack.push(7);
// stack.print();
// Queue implemented using LinkedList
function Queue() {
this.head = null;
this.tail = null;
}
Queue.prototype.enqueue = function(data) {
var newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}
Queue.prototype.dequeue = function() {
var newNode;
if (this.head !== null) {
newNode = this.head.data;
this.head = this.head.next;
}
return newNode;
}
Queue.prototype.print = function() {
var curr = this.head;
while (curr) {
console.log(curr.data);
curr = curr.next;
}
}
var queue = new Queue();
queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.print();
queue.dequeue();
queue.dequeue();
queue.print();- Rohit
16
如其他答案所述，堆栈的实现很简单。
然而，在这个帖子中，我没有找到任何令人满意的JavaScript队列实现答案，所以我自己写了一个。
这个帖子中有三种类型的解决方案：
- 数组 - 最糟糕的解决方案，对大型数组使用
array.shift()非常低效。 - 链表 - 它是O(1)，但为每个元素使用一个对象有点过度，特别是如果它们很多并且很小，比如存储数字。
- 延迟移位数组 - 它包括将索引与数组关联。当一个元素被出列时，索引向前移动。当索引达到数组的中间时，数组被切成两半以删除第一半。
在我看来，延迟移位数组是最令人满意的解决方案，但它们仍然将所有内容存储在一个大的连续数组中，这可能会有问题，并且当数组被切割时，应用程序会停顿。
我使用由小型数组（每个数组最多1000个元素）组成的链表进行了实现。这些数组的行为类似于延迟移位数组，除了它们从不被切割：当数组中的每个元素都被删除时，数组被简单地丢弃。
这个包在npm上有基本的FIFO功能，我最近才推出。代码分为两部分。
这是第一部分：
/** Queue contains a linked list of Subqueue */
class Subqueue <T> {
public full() {
return this.array.length >= 1000;
}
public get size() {
return this.array.length - this.index;
}
public peek(): T {
return this.array[this.index];
}
public last(): T {
return this.array[this.array.length-1];
}
public dequeue(): T {
return this.array[this.index++];
}
public enqueue(elem: T) {
this.array.push(elem);
}
private index: number = 0;
private array: T [] = [];
public next: Subqueue<T> = null;
}
下面是主要的Queue类：
class Queue<T> {
get length() {
return this._size;
}
public push(...elems: T[]) {
for (let elem of elems) {
if (this.bottom.full()) {
this.bottom = this.bottom.next = new Subqueue<T>();
}
this.bottom.enqueue(elem);
}
this._size += elems.length;
}
public shift(): T {
if (this._size === 0) {
return undefined;
}
const val = this.top.dequeue();
this._size--;
if (this._size > 0 && this.top.size === 0 && this.top.full()) {
// Discard current subqueue and point top to the one after
this.top = this.top.next;
}
return val;
}
public peek(): T {
return this.top.peek();
}
public last(): T {
return this.bottom.last();
}
public clear() {
this.bottom = this.top = new Subqueue();
this._size = 0;
}
private top: Subqueue<T> = new Subqueue();
private bottom: Subqueue<T> = this.top;
private _size: number = 0;
}
类型注解（: X）可以轻松地删除，以获得ES6 JavaScript代码。
- coyotte508
15
Javascript数组的shift()方法在存储许多元素时速度很慢。我知道两种实现具有分摊O(1)复杂度的队列的方式。
第一种方法是使用循环缓冲区和表倍增。我以前已经实现过这个，你可以在这里看到我的源代码：https://github.com/kevyuu/rapid-queue
第二种方法是使用两个栈来实现。下面是使用两个栈实现队列的代码：
function createDoubleStackQueue() {
var that = {};
var pushContainer = [];
var popContainer = [];
function moveElementToPopContainer() {
while (pushContainer.length !==0 ) {
var element = pushContainer.pop();
popContainer.push(element);
}
}
that.push = function(element) {
pushContainer.push(element);
};
that.shift = function() {
if (popContainer.length === 0) {
moveElementToPopContainer();
}
if (popContainer.length === 0) {
return null;
} else {
return popContainer.pop();
}
};
that.front = function() {
if (popContainer.length === 0) {
moveElementToPopContainer();
}
if (popContainer.length === 0) {
return null;
}
return popContainer[popContainer.length - 1];
};
that.length = function() {
return pushContainer.length + popContainer.length;
};
that.isEmpty = function() {
return (pushContainer.length + popContainer.length) === 0;
};
return that;}
这是使用jsPerf进行的性能比较
CircularQueue.shift()与Array.shift()的比较
http://jsperf.com/rapidqueue-shift-vs-array-shift
从结果可以看出，处理大型数据集时速度明显更快。
- kevinyu
2
哪个更快？你的 jsperf 链接无法使用。 - Luke Hutchison
10
您可以基于这个概念使用自己定制的类，以下是您可以使用的代码片段来完成此操作。
/*
* Stack implementation in JavaScript
*/
function Stack() {
this.top = null;
this.count = 0;
this.getCount = function() {
return this.count;
}
this.getTop = function() {
return this.top;
}
this.push = function(data) {
var node = {
data: data,
next: null
}
node.next = this.top;
this.top = node;
this.count++;
}
this.peek = function() {
if (this.top === null) {
return null;
} else {
return this.top.data;
}
}
this.pop = function() {
if (this.top === null) {
return null;
} else {
var out = this.top;
this.top = this.top.next;
if (this.count > 0) {
this.count--;
}
return out.data;
}
}
this.displayAll = function() {
if (this.top === null) {
return null;
} else {
var arr = new Array();
var current = this.top;
//console.log(current);
for (var i = 0; i < this.count; i++) {
arr[i] = current.data;
current = current.next;
}
return arr;
}
}
}
为了检查这个问题，请使用您的控制台并逐行尝试以下内容。
>> var st = new Stack();
>> st.push("BP");
>> st.push("NK");
>> st.getTop();
>> st.getCount();
>> st.displayAll();
>> st.pop();
>> st.displayAll();
>> st.getTop();
>> st.peek();
- jforjs
1
2对于命名规范的反对意见：以大写字母开头的方法被认为是构造函数。 - Pavlo
9
您可以使用多种方法在Javascript中实现堆栈（Stacks）和队列（Queues）。上面的大部分答案都是相当肤浅的实现，我将尝试实现更易读且更健壮的内容（使用es6的新语法特性）。
以下是堆栈（Stack）的实现：
class Stack {
constructor(...items){
this._items = []
if(items.length>0)
items.forEach(item => this._items.push(item) )
}
push(...items){
//push item to the stack
items.forEach(item => this._items.push(item) )
return this._items;
}
pop(count=0){
//pull out the topmost item (last item) from stack
if(count===0)
return this._items.pop()
else
return this._items.splice( -count, count )
}
peek(){
// see what's the last item in stack
return this._items[this._items.length-1]
}
size(){
//no. of items in stack
return this._items.length
}
isEmpty(){
// return whether the stack is empty or not
return this._items.length==0
}
toArray(){
return this._items;
}
}
这是如何使用堆栈的示例代码：
let my_stack = new Stack(1,24,4);
// [1, 24, 4]
my_stack.push(23)
//[1, 24, 4, 23]
my_stack.push(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_stack.pop();
//[1, 24, 4, 23, 1, 2]
my_stack.pop(3)
//[1, 24, 4]
my_stack.isEmpty()
// false
my_stack.size();
//3
如果您想查看有关此实现的详细说明以及如何进一步改进它的内容，您可以在这里阅读：http://jschap.com/data-structures-in-javascript-stack/ 以下是 es6 中队列实现的代码：
class Queue{
constructor(...items){
//initialize the items in queue
this._items = []
// enqueuing the items passed to the constructor
this.enqueue(...items)
}
enqueue(...items){
//push items into the queue
items.forEach( item => this._items.push(item) )
return this._items;
}
dequeue(count=1){
//pull out the first item from the queue
this._items.splice(0,count);
return this._items;
}
peek(){
//peek at the first item from the queue
return this._items[0]
}
size(){
//get the length of queue
return this._items.length
}
isEmpty(){
//find whether the queue is empty or no
return this._items.length===0
}
}
以下是如何使用此实现的方法：
let my_queue = new Queue(1,24,4);
// [1, 24, 4]
my_queue.enqueue(23)
//[1, 24, 4, 23]
my_queue.enqueue(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_queue.dequeue();
//[24, 4, 23, 1, 2, 342]
my_queue.dequeue(3)
//[1, 2, 342]
my_queue.isEmpty()
// false
my_queue.size();
//3
如果您想了解这些数据结构是如何实现的以及如何进一步改进它们，可以参考jschap.com的“使用javascript玩转数据结构”系列教程。以下是队列的链接 - http://jschap.com/playing-data-structures-javascript-queues/
- Anish K.
9
我很喜欢认为实现栈和队列最干净的方式应该是使用一个容器，允许从两端添加和删除，然后限制其一端的功能，可以通过在JavaScript中使用简单的数组来完成。
// 封装时使用的语句
// 封装时使用的语句
// Allow push and pop from the same end
array.push(element);
array.pop();
// 封装队列容器时使用的语句
// Allow push and pop from different ends
array.push(element);
array.shift();
- Mayank Narula
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接