在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
如果有人需要它,你可以使用这个NPM包https://www.npmjs.com/package/data-structures-typescript,它有一个队列和堆栈,它支持javascript和typescript,它是通用的,所以你可以用你自己的值类型;)
其他回答
使用两个堆栈构造一个队列。
O(1)用于入队和出队操作。
class Queue {
constructor() {
this.s1 = []; // in
this.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());
}
}
}
或者可以使用两个数组来实现队列数据结构。
var temp_stack = new Array();
var stack = new Array();
temp_stack.push(1);
temp_stack.push(2);
temp_stack.push(3);
如果我现在弹出元素,那么输出将是3 2 1。 但我们想先进先出结构,所以你可以做以下。
stack.push(temp_stack.pop());
stack.push(temp_stack.pop());
stack.push(temp_stack.pop());
stack.pop(); //Pop out 1
stack.pop(); //Pop out 2
stack.pop(); //Pop out 3
单端队列
这是一个使用映射的队列。由于插入顺序得到了保证,所以可以像迭代数组一样迭代它。除此之外,它的思想与Queue.js非常相似。
我做了一些简单的测试,但还没有进行广泛的测试。我还添加了一些我认为很好的功能(通过数组构造)或易于实现(例如last()和first())。
它背后的简单版本/直觉如下:
class Queue {
constructor() {
this.offset = 0
this.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
}
}
简单版本的问题是,当内存索引超过9千万亿(Number.MAX_SAFE_INTEGER的值)时,需要重新映射内存。此外,我认为它可能很好有数组构造,它很高兴看到值正在进入队列和退出队列返回。可以通过编写以下代码来解释这一点:
class Queue {
constructor() {
this.offset = 0
this.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 = undefined
if (this.length() > 0) {
result = this.data.get(this.offset)
this.data.delete(this.offset)
this.offset += 1
}
if (this.length() === 0) this.offset = 0
return 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 = 0
for (const [key, value] of this.data) {
this.data.set(this.offset, value)
this.data.delete(key, value)
this.offset += 1
if (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 typing
q = 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)
我在实现BFS时遇到了这个线程。在疑惑为何表现如此糟糕之后,我做了一些调查。array.shift()通常在O(n)中运行,这将我的BFS运行时从O(V+E)增加到O(V^2+E)。
我没有从头开始实现一个队列,而是使用了npm包双端队列,它与之前使用的数组方法兼容,工作起来很有魅力。 deque可以用作堆栈或队列。
//import package
import Deque from 'double-ended-queue';
//create queue
let queue = new Deque();
//append
queue.push(item);
//dequeue (get first item inserted)
let firstItem = queue.shift();
//pop (get last item inserted)
let lastItem = queue.pop();
下面是一个队列的链表版本,它也包括最后一个节点,这是@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 same
this.first = node;
this.last = node;
} else { // otherwise we stick it on the end
this.last.next=node;
this.last=node;
}
this.size += 1;
return node;
};
Queue.prototype.dequeue = function() {
if (!this.first) //check for empty list
return null;
temp = this.first; // grab top of list
if (this.first==this.last) {
this.last=null; // when we need to pop the last one
}
this.first = this.first.next; // move top of list down
this.size -= 1;
return temp;
};