如何在JavaScript中实现堆栈和队列？

在JavaScript中实现堆栈和队列的最佳方法是什么？

我想做调车场算法，我需要这些数据结构。

548836 次浏览
小开
最佳答案 
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技巧”

小开

数组。

堆栈：

var stack = [];
//put value on top of stackstack.push(1);
//remove value from top of stackvar value = stack.pop();

队列：

var queue = [];
//put value on end of queuequeue.push(1);
//Take first value from queuevar value = queue.shift();
小开

JavaScript中的常规数组结构是一个堆栈（先进，后出），也可以用作队列（先进，先出），具体取决于您进行的调用。

检查此链接以了解如何使数组像队列一样工作：

队列

小开

Javascript有推送和弹出方法，它们对普通的Javascript数组对象进行操作。

对于队列，看这里：

http://safalra.com/web-design/javascript/queues/

队列可以在JavaScript使用推送和Shift方法或取消Shift和pop数组对象的方法。虽然这是一个简单的方法来实现队列，这是非常低效的大队列-因为方法对数组进行操作，移位和unShift方法将每个元素移动到每次调用它们时的数组。

Queue.js是JavaScript的一个简单高效的队列实现，其出列函数以摊销常数时间运行。因此，对于更大的队列，它可以比使用数组快得多。

小开

创建一对类，它们提供这些数据结构中的每一个都具有的各种方法（ush、pop、peek等）。现在实现这些方法。如果你熟悉堆栈/队列背后的概念，这应该很简单。你可以用数组实现堆栈，用链表实现队列，尽管肯定还有其他方法可以实现。Javascript会让这变得容易，因为它是弱类型的，所以你甚至不必担心泛型类型，如果你用Java或C#实现它，你甚至不必担心泛型类型。

小开

或者您可以使用两个数组来实现队列数据结构。

var temp_stack = new Array();var stack = new Array();
temp_stack.push(1);temp_stack.push(2);temp_stack.push(3);

如果我现在弹出元素，那么输出将是3,2,1。但是我们想要FIFO结构，所以你可以做以下事情。

stack.push(temp_stack.pop());stack.push(temp_stack.pop());stack.push(temp_stack.pop());
stack.pop(); //Pop out 1stack.pop(); //Pop out 2stack.pop(); //Pop out 3
小开

你可以根据这个概念使用你自己的自定义类，这里是你可以用来做这些事情的代码片段

/**   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();
小开

没有数组 

//Javascript stack linked list data structure (no array)
function node(value, noderef) {this.value = value;this.next = noderef;}function stack() {this.push = function (value) {this.next = this.first;this.first = new node(value, this.next);}this.pop = function () {var popvalue = this.first.value;this.first = this.first.next;return popvalue;}this.hasnext = function () {return this.next != undefined;}this.isempty = function () {return this.first == undefined;}
}
//Javascript stack linked list data structure (no array)function node(value, noderef) {this.value = value;this.next = undefined;}function queue() {this.enqueue = function (value) {this.oldlast = this.last;this.last = new node(value);if (this.isempty())this.first = this.last;elsethis.oldlast.next = this.last;}this.dequeue = function () {var queuvalue = this.first.value;this.first = this.first.next;return queuvalue;}this.hasnext = function () {return this.first.next != undefined;}this.isempty = function () {return this.first == undefined;}
}
小开

如果您了解带有推（）和弹出（）函数的堆栈，那么队列只是在oposite意义上进行这些操作之一。推（）的反义词是unShift（），oposite的op（）es Shift（）。然后：

//classic stackvar stack = [];stack.push("first"); // push inserts at the endstack.push("second");stack.push("last");stack.pop(); //pop takes the "last" element
//One way to implement queue is to insert elements in the oposite sense than a stackvar queue = [];queue.unshift("first"); //unshift inserts at the beginningqueue.unshift("second");queue.unshift("last");queue.pop(); //"first"
//other way to do queues is to take the elements in the oposite sense than stackvar queue = [];queue.push("first"); //push, as in the stack inserts at the endqueue.push("second");queue.push("last");queue.shift(); //but shift takes the "first" element
小开

如果你想创建自己的数据结构，你可以构建自己的：

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;};
小开

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（）vsArray.shift（）

http://jsperf.com/rapidqueue-shift-vs-array-shift

正如你所看到的，它在大数据集上显着更快

小开

这是我使用链表实现的堆栈和队列：

// Linked Listfunction Node(data) {this.data = data;this.next = null;}
// Stack implemented using LinkedListfunction Stack() {this.top = null;}
Stack.prototype.push = function(data) {var newNode = new Node(data);
newNode.next = this.top; //Special attentionthis.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 LinkedListfunction 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();

小开 
/*------------------------------------------------------------------Defining Stack Operations using Closures in Javascript, privacy andstate of stack operations are maintained
@author:Arijt BasuLog: Sun Dec 27, 2015, 3:25PM-------------------------------------------------------------------*/var stackControl = true;var stack = (function(array) {array = [];//--Define the max size of the stackvar MAX_SIZE = 5;
function isEmpty() {if (array.length < 1) console.log("Stack is empty");};isEmpty();
return {
push: function(ele) {if (array.length < MAX_SIZE) {array.push(ele)return array;} else {console.log("Stack Overflow")}},pop: function() {if (array.length > 1) {array.pop();return array;} else {console.log("Stack Underflow");}}
}})()// var list = 5;// console.log(stack(list))if (stackControl) {console.log(stack.pop());console.log(stack.push(3));console.log(stack.push(2));console.log(stack.pop());console.log(stack.push(1));console.log(stack.pop());console.log(stack.push(38));console.log(stack.push(22));console.log(stack.pop());console.log(stack.pop());console.log(stack.push(6));console.log(stack.pop());}//End of STACK Logic
/* Defining Queue operations*/
var queue = (function(array) {array = [];var reversearray;//--Define the max size of the stackvar MAX_SIZE = 5;
function isEmpty() {if (array.length < 1) console.log("Queue is empty");};isEmpty();
return {insert: function(ele) {if (array.length < MAX_SIZE) {array.push(ele)reversearray = array.reverse();return reversearray;} else {console.log("Queue Overflow")}},delete: function() {if (array.length > 1) {//reversearray = array.reverse();array.pop();return array;} else {console.log("Queue Underflow");}}}


})()
console.log(queue.insert(5))console.log(queue.insert(3))console.log(queue.delete(3))
小开

这是一个相当简单的队列实现，有两个目标：

  • 与array.shift（）不同，您知道这个出列方法需要恒定的时间（O（1））。
  • 为了提高速度，这种方法比链表方法使用更少的分配。

堆栈实现仅共享第二个目标。

// Queuefunction Queue() {this.q = new Array(5);this.first = 0;this.size = 0;}Queue.prototype.enqueue = function(a) {var other;if (this.size == this.q.length) {other = new Array(this.size*2);for (var i = 0; i < this.size; i++) {other[i] = this.q[(this.first+i)%this.size];}this.first = 0;this.q = other;}this.q[(this.first+this.size)%this.q.length] = a;this.size++;};Queue.prototype.dequeue = function() {if (this.size == 0) return undefined;this.size--;var ret = this.q[this.first];this.first = (this.first+1)%this.q.length;return ret;};Queue.prototype.peek = function() { return this.size > 0 ? this.q[this.first] : undefined; };Queue.prototype.isEmpty = function() { return this.size == 0; };
// Stackfunction Stack() {this.s = new Array(5);this.size = 0;}Stack.prototype.push = function(a) {var other;if (this.size == this.s.length) {other = new Array(this.s.length*2);for (var i = 0; i < this.s.length; i++) other[i] = this.s[i];this.s = other;}this.s[this.size++] = a;};Stack.prototype.pop = function() {if (this.size == 0) return undefined;return this.s[--this.size];};Stack.prototype.peek = function() { return this.size > 0 ? this.s[this.size-1] : undefined; };
小开

这是队列的链表版本，它还包括最后一个节点，正如@perkins建议的那样，这是最合适的。

// QUEUE Object Definition
var Queue = function() {this.first = null;this.last = 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){ // for empty list first and last are the samethis.first = node;this.last = node;} else { // otherwise we stick it on the endthis.last.next=node;this.last=node;}
this.size += 1;return node;};
Queue.prototype.dequeue = function() {if (!this.first) //check for empty listreturn null;
temp = this.first; // grab top of listif (this.first==this.last) {this.last=null;  // when we need to pop the last one}this.first = this.first.next; // move top of list downthis.size -= 1;return temp;};
小开 
  var x = 10;var y = 11;var Queue = new Array();Queue.unshift(x);Queue.unshift(y);
console.log(Queue)// Output [11, 10]
Queue.pop()console.log(Queue)// Output [11]
小开

在JavaScript中有很多方法可以实现堆栈和队列。上面的大多数答案都是非常肤浅的实现，我会尝试实现一些更具可读性（使用es6的新语法特性）和健壮的东西。

这是堆栈实现：

class Stack {constructor(...items){this._items = []
if(items.length>0)items.forEach(item => this._items.push(item) )
}
push(...items){//push item to the stackitems.forEach(item => this._items.push(item) )return this._items;
}
pop(count=0){//pull out the topmost item (last item) from stackif(count===0)return this._items.pop()elsereturn this._items.splice( -count, count )}
peek(){// see what's the last item in stackreturn this._items[this._items.length-1]}
size(){//no. of items in stackreturn this._items.length}
isEmpty(){// return whether the stack is empty or notreturn 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()// falsemy_stack.size();//3

如果您想查看有关此实现的详细描述以及如何进一步改进，您可以在此处阅读：http://jschap.com/data-structures-in-javascript-stack/

以下是es6中队列实现的代码：

class Queue{constructor(...items){//initialize the items in queuethis._items = []// enqueuing the items passed to the constructorthis.enqueue(...items)}
enqueue(...items){//push items into the queueitems.forEach( item => this._items.push(item) )return this._items;}
dequeue(count=1){//pull out the first item from the queuethis._items.splice(0,count);return this._items;}
peek(){//peek at the first item from the queuereturn this._items[0]}
size(){//get the length of queuereturn this._items.length}
isEmpty(){//find whether the queue is empty or noreturn 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()// falsemy_queue.size();//3

要了解这些数据结构是如何实现的以及如何进一步改进这些数据结构的完整教程，您可能希望在jschap.com浏览“在javascript中使用数据结构”系列。这是队列的链接-http://jschap.com/playing-data-structures-javascript-queues/

小开

这是我的堆栈实现。

function Stack() {this.dataStore = [];this.top = 0;this.push = push;this.pop = pop;this.peek = peek;this.clear = clear;this.length = length;}function push(element) {this.dataStore[this.top++] = element;}function peek() {return this.dataStore[this.top-1];}function pop() {return this.dataStore[--this.top];}function clear() {this.top = 0;}function length() {return this.top;}
var s = new Stack();s.push("David");s.push("Raymond");s.push("Bryan");console.log("length: " + s.length());console.log(s.peek());
小开

在我看来，内置数组对于堆栈来说很好。如果你想要TypeScript中的队列，这里是一个实现

/*** A Typescript implementation of a queue.*/export default class Queue {
private queue = [];private offset = 0;
constructor(array = []) {// Init the queue using the contents of the arrayfor (const item of array) {this.enqueue(item);}}
/*** @returns {number} the length of the queue.*/public getLength(): number {return (this.queue.length - this.offset);}
/*** @returns {boolean} true if the queue is empty, and false otherwise.*/public isEmpty(): boolean {return (this.queue.length === 0);}
/*** Enqueues the specified item.** @param item - the item to enqueue*/public enqueue(item) {this.queue.push(item);}
/***  Dequeues an item and returns it. If the queue is empty, the value* {@code null} is returned.** @returns {any}*/public dequeue(): any {// if the queue is empty, return immediatelyif (this.queue.length === 0) {return null;}
// store the item at the front of the queueconst item = this.queue[this.offset];
// increment the offset and remove the free space if necessaryif (++this.offset * 2 >= this.queue.length) {this.queue = this.queue.slice(this.offset);this.offset = 0;}
// return the dequeued itemreturn item;};
/*** Returns the item at the front of the queue (without dequeuing it).* If the queue is empty then {@code null} is returned.** @returns {any}*/public peek(): any {return (this.queue.length > 0 ? this.queue[this.offset] : null);}
}

这里有一个Jest测试

it('Queue', () => {const queue = new Queue();expect(queue.getLength()).toBe(0);expect(queue.peek()).toBeNull();expect(queue.dequeue()).toBeNull();
queue.enqueue(1);expect(queue.getLength()).toBe(1);queue.enqueue(2);expect(queue.getLength()).toBe(2);queue.enqueue(3);expect(queue.getLength()).toBe(3);
expect(queue.peek()).toBe(1);expect(queue.getLength()).toBe(3);expect(queue.dequeue()).toBe(1);expect(queue.getLength()).toBe(2);
expect(queue.peek()).toBe(2);expect(queue.getLength()).toBe(2);expect(queue.dequeue()).toBe(2);expect(queue.getLength()).toBe(1);
expect(queue.peek()).toBe(3);expect(queue.getLength()).toBe(1);expect(queue.dequeue()).toBe(3);expect(queue.getLength()).toBe(0);
expect(queue.peek()).toBeNull();expect(queue.dequeue()).toBeNull();});

希望有人觉得这个有用，

干杯，

斯图

小开

堆栈实现是微不足道的，如其他答案中所述。

然而，我在这个线程中没有找到任何令人满意的答案来实现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 afterthis.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代码。

小开

如果您正在寻找具有一些基本操作（基于链表）的Stack和Queue数据结构的ES6 OOP实现，那么它可能如下所示：

Queue.js

import LinkedList from '../linked-list/LinkedList';
export default class Queue {constructor() {this.linkedList = new LinkedList();}
isEmpty() {return !this.linkedList.tail;}
peek() {if (!this.linkedList.head) {return null;}
return this.linkedList.head.value;}
enqueue(value) {this.linkedList.append(value);}
dequeue() {const removedHead = this.linkedList.deleteHead();return removedHead ? removedHead.value : null;}
toString(callback) {return this.linkedList.toString(callback);}}

Stack.js

import LinkedList from '../linked-list/LinkedList';
export default class Stack {constructor() {this.linkedList = new LinkedList();}
/*** @return {boolean}*/isEmpty() {return !this.linkedList.tail;}
/*** @return {*}*/peek() {if (!this.linkedList.tail) {return null;}
return this.linkedList.tail.value;}
/*** @param {*} value*/push(value) {this.linkedList.append(value);}
/*** @return {*}*/pop() {const removedTail = this.linkedList.deleteTail();return removedTail ? removedTail.value : null;}
/*** @return {*[]}*/toArray() {return this.linkedList.toArray().map(linkedListNode => linkedListNode.value).reverse();}
/*** @param {function} [callback]* @return {string}*/toString(callback) {return this.linkedList.toString(callback);}}

上面示例中用于堆栈和队列的LinkedList实现可以在在github这里中找到。

小开

祝好

在JavaScript中，栈和队列的实现如下：

堆栈：堆栈是根据后进先出（LIFO）原则插入和删除的对象的容器。

  • 方法将一个或多个元素添加到数组的末尾并返回数组的新长度。
  • 方法从数组中删除最后一个元素并返回该元素。

队列：队列是根据先进先出（FIFO）原则插入和删除的对象（线性集合）的容器。

  • 方法将一个或多个元素添加到数组的开头。

  • Shift：该方法从数组中删除第一个元素。

let stack = [];stack.push(1);//[1]stack.push(2);//[1,2]stack.push(3);//[1,2,3] 
console.log('It was inserted 1,2,3 in stack:', ...stack);
stack.pop(); //[1,2]console.log('Item 3 was removed:', ...stack);
stack.pop(); //[1]console.log('Item 2 was removed:', ...stack);

let queue = [];queue.push(1);//[1]queue.push(2);//[1,2]queue.push(3);//[1,2,3]
console.log('It was inserted 1,2,3 in queue:', ...queue);
queue.shift();// [2,3]console.log('Item 1 was removed:', ...queue);
queue.shift();// [3]console.log('Item 2 was removed:', ...queue);

小开

您可以使用WeakMaps在ES6类中实现私有属性以及JavaScript语言中String特性和方法的好处，如下所示：

const _items = new WeakMap();
class Stack {constructor() {_items.set(this, []);}
push(obj) {_items.get(this).push(obj);}
pop() {const L = _items.get(this).length;if(L===0)throw new Error('Stack is empty');return _items.get(this).pop();}
peek() {const items = _items.get(this);if(items.length === 0)throw new Error ('Stack is empty');return items[items.length-1];}
get count() {return _items.get(this).length;}}
const stack = new Stack();
//now in console://stack.push('a')//stack.push(1)//stack.count   => 2//stack.peek()  => 1//stack.pop()   => 1//stack.pop()   => "a"//stack.count   => 0//stack.pop()   => Error Stack is empty
小开

使用两个堆栈构造一个队列。

O（1）用于入队和出队操作。

class Queue {constructor() {this.s1 = []; // inthis.s2 = []; // out}
enqueue(val) {this.s1.push(val);}
dequeue() {if (this.s2.length === 0) {this._move();}
return this.s2.pop(); // return undefined if empty}
_move() {while (this.s1.length) {this.s2.push(this.s1.pop());}}}
小开

有点晚的回答，但我认为这个答案应该在这里。这是一个使用稀疏数组幂的具有O（1）enqueue和O（1）dequeue的Queue的实现。

JS中的稀疏数组大多被忽视，但它们实际上是一个宝石，我们应该在一些关键任务中使用它们的功能。

所以这里有一个骨架Queue实现，它扩展了Array类型并一直在O（1）中执行它的事情。

class Queue extends Array {constructor(){super()Object.defineProperty(this,"head",{ value   : 0, writable: true});}enqueue(x) {this.push(x);return this;}dequeue() {var first;return this.head < this.length ? ( first = this[this.head], delete this[this.head++], first): void 0; // perfect undefined}peek() {return this[this.head];}}
var q = new Queue();console.log(q.dequeue());      // doesn't breakconsole.log(q.enqueue(10));    // add 10console.log(q.enqueue("DIO")); // add "DIO" (Last In Line cCc R.J.DIO reis cCc)console.log(q);                // display qconsole.log(q.dequeue());      // lets get the first one in the lineconsole.log(q.dequeue());      // lets get DIO out from the line
.as-console-wrapper {max-height: 100% !important;}

所以我们这里有潜在的内存泄漏吗？不，我不这么认为。JS稀疏数组是不连续的。因此，删除的项目不应该是数组内存占用的一部分。让GC为你做它的工作。它是免费的。

一个潜在的问题是，当您不断将项目加入队列时，length属性会无限增长。然而，仍然可以实现自动刷新（压缩）机制，一旦长度达到某个值就启动。

编辑：

上面的代码如果很好，但是delete运算符虽然仍然是O（1），但速度很慢。此外，现代JS引擎经过了如此优化，以至于对于<~25000项.shift()无论如何都可以工作O（1）。所以我们需要更好的东西。

在这种特殊情况下，随着引擎的发展，我们必须利用它们的新功能。下面的代码使用链表，我相信它是截至2021年最快、最安全的现代JS队列结构。

class Queue {#head;#last;constructor(){this.#head;this.#last;};enqueue(value){var link = {value, next: void 0};this.#last = this.#head ? this.#last.next = link: this.#head      = link;}dequeue(){var first;return this.#head && ( first = this.#head.value, this.#head = this.#head.next, first);}peek(){return this.#head && this.#head.value;}};

这是一个非常快的Queue结构，并使用私有类字段来隐藏关键变量以防窥探。

小开

单端队列

这是一个使用map的队列。由于插入顺序是保证，您可以像数组一样迭代它。除此之外，这个想法与Queue.js非常相似。

我做了一些简单的测试，但还没有广泛测试。我还添加了一些我认为不错（通过数组构建）或易于实现（例如last()和first()）的功能。

它背后的简单版本/直觉如下：

class Queue {constructor() {this.offset = 0this.data = new Map()}
enqueue(item) {const current = this.offset + this.length()this.data.set(current, item)}
dequeue() {if (this.length() > 0) {this.data.delete(this.offset)this.offset += 1}}
first() {return this.data.get(this.offset)}
last() {return this.data.get(this.offset + this.length() - 1)}
length() {return this.data.size}}

简单版本的问题是，当内存索引超过大约9000万亿（Number.MAX_SAFE_INTEGER的值）时，需要重新映射。此外，我认为有数组结构可能会很好，并且很高兴看到正在入列和出列的值被返回。可以通过编写以下代码来解释这一点：

class Queue {constructor() {this.offset = 0this.data = new Map()if (arguments.length === 1) this._initializeFromArray(arguments[0])}
enqueue(item) {const current = this.offset + this.length()this.data.set(current, item)let result = this.data.get(current)this._remapDataIfMaxMemoryViolation(current, Number.MAX_SAFE_INTEGER)return result}
dequeue() {let result = undefinedif (this.length() > 0) {result = this.data.get(this.offset)this.data.delete(this.offset)this.offset += 1}if (this.length() === 0) this.offset = 0return result}
first() {return this.data.get(this.offset)}
last() {return this.data.get(this.offset + this.length() - 1)}
length() {return this.data.size}
_remapDataIfMaxMemoryViolation(current, threshhold) {if (current+1 === threshhold) {const length = this.length()this.offset = 0for (const [key, value] of this.data) {this.data.set(this.offset, value)this.data.delete(key, value)this.offset += 1if (this.offset === length) break}}}
_initializeFromArray(array) {for (const value of array) {this.data.set(this.offset, value)this.offset += 1}}}

我在Chrome开发者控制台中进行了一些测试，并在完整版本上进行了以下调用。

l = console.log // I'm lazy with typingq = new Queue()l('enqueue', q.enqueue(1))l('enqueue', q.enqueue(2))l('enqueue', q.enqueue(3))l('enqueue', q.enqueue("hello"))l('enqueue', q.enqueue("monkey"))l('show 5 elements: ', q.data)l('length', q.length())l('first', q.first())l('last', q.last())l('dequeue', q.dequeue())l('dequeue', q.dequeue())l('show 3 elements', q.data)q._remapDataIfMaxMemoryViolation(q.length()+q.offset-1, 5)l('show 3 remapped elements', q.data)
l(queue = new Queue([3,4,5,6,7,8,9]))l(queue.data)
小开

我认为实现堆栈和队列的最干净的方法应该是使用一个容器，允许从两端添加和删除，然后限制其一端的功能，这可以通过JavaScript中的一个简单数组来完成。

//堆垛容器封装时使用的报表

// Allow push and pop from the same endarray.push(element);array.pop();

//包裹时在队列容器中使用的语句

// Allow push and pop from different endsarray.push(element);array.shift();
小开

很抱歉碰到这个话题，但我滚动了许多答案，没有看到任何基于对象的队列的实现，它可以以O（1）执行入队和出队，而不会浪费内存。

Dmitri Pavlutin在他的博客上有一个不错的启动代码https://dmitripavlutin.com/javascript-queue/

它只错过了一个0长度检查，这对于添加来说是微不足道的。

这个解决方案的最大和唯一的问题是不断增长的指数，如果队列长时间和/或高速运行（我的意图是处理音频=高速），它可能会在某一点上达到某个数字限制。

对此没有完美的解决方案……简单的方法可以是在队列为空时将索引重置为0。

最后，我添加了一个refactor方法，它将所有索引移回开头，以便在队列永远不为空的情况下使用。

性能无疑更好（该数字是以毫秒为单位的时间，用于排队10,000个号码然后将其退出排队）：输入图片描述

class QueueObject {constructor () {this.data = {}this.head = 0this.tail = 0this.length = 0}enqueue (value) {this.data[this.tail++] = valuethis.length++}dequeue () {let valueif (this.length > 0) {this.length--value = this.data[this.head]delete this.data[this.head++]} else {this.head = 0this.tail = 0value = null}return value}refactor () {if (this.head > 0) {for (let i = this.head; i < this.tail; i++) {this.data[i - this.head] = this.data[i]delete this.data[i]}this.tail = this.lengththis.head = 0}}}
小开

我在实现BFS时遇到了这个线程。在想知道为什么性能如此差之后，我做了一些研究。array.shift（）通常以O（n）运行，这将我的BFS运行时从O（V+E）增加到O（V^2+E）。

我没有从头开始实现队列，而是使用了npm包双端队列，它与以前使用的数组方法兼容，并且工作起来很有魅力。双端队列可以用作堆栈或队列。

    //import packageimport Deque from 'double-ended-queue';
//create queuelet queue = new Deque();//appendqueue.push(item);//dequeue (get first item inserted)let firstItem = queue.shift();
//pop (get last item inserted)let lastItem = queue.pop();
小开

数组是Javascript中的堆栈。只需使用arr.push(x)和y = arr.pop()。

这是在Javascript中实现队列的最简单方法，该队列的enqueue(x)和y = dequeue()的摊销时间均为O(1)。它使用从插入索引到元素的映射。

function newQueue() {return {headIdx: 0,tailIdx: 0,elts: {},enqueue: (elt) => queue.elts[queue.tailIdx++] = elt,dequeue: () => {if (queue.headIdx == queue.tailIdx) {throw new Error("Queue is empty");}return queue.elts[queue.headIdx++];},size: () => queue.tailIdx - queue.headIdx,isEmpty: () => queue.tailIdx == queue.headIdx};}

使用链表实现的队列比这种基于映射的方法更有效，使用循环缓冲区实现的队列比这种基于映射的方法更有效，但这两种数据结构的实现更复杂（尤其是循环缓冲区数据结构）。

小开

如果其他人需要它，你可以使用这个NPM包https://www.npmjs.com/package/data-structures-typescript，它有一个队列和堆栈，它支持JavaScript和TypeScript，它是通用的，所以你可以用你自己的值类型来使用它；）

小开

正如许多人所说：使用push和pop的本机数组对于堆栈来说很好，但是shift从队列中获取元素需要移动剩余的元素，这可能会使它变慢。在kevinyu的回答中使用两个堆栈来制作队列的想法是一个很好的主意来修复它，当然这也可以用native-array-stacks来完成。（编辑：实际上已经有Yuki-Dreamer的回答这样做了，尽管不那么紧凑。直到现在我才注意到它，因为它被不公平地否决了。）

这是一个使用一些ES5/ES6特性的紧凑实现，使队列对象的行为尽可能接近本机-push/shift变体，除了每次操作需要摊销O（1）时间：

const queue = () => {const a = [], b = [];return {push: (...elts) => a.push(...elts),shift: () => {if (b.length === 0) {while (a.length > 0) { b.push(a.pop()) }}return b.pop();},get length() { return a.length + b.length }}}

现在你可以做：

const q = queue();q.push(8);q.push(9);q.push(10);console.log(q.shift());         // outputs 8q.push(11);console.log(q.shift());         // outputs 9console.log(q.shift());         // outputs 10console.log(q.shift());         // outputs 11console.log(q.shift());         // outputs undefined

queue实现使用length的吸气剂语法，使其看起来像一个属性，使用休息参数语法进行推送，允许一次推送多个内容。如果您不希望这样，您可以将第4行替换为push: elt => a.push(elt),。然而，请注意，您可以没有将其替换为push: a.push,，就像我自己首先尝试的那样，结果非常奇怪：这是因为它会导致调用本机推送方法，并将this设置为队列对象。


提交答案