在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
单端队列
这是一个使用映射的队列。由于插入顺序得到了保证，所以可以像迭代数组一样迭代它。除此之外，它的思想与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)
其他回答
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() vs Array.shift()
http://jsperf.com/rapidqueue-shift-vs-array-shift
正如你所看到的，大数据集的速度要快得多
有很多方法可以在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 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/
单端队列
这是一个使用映射的队列。由于插入顺序得到了保证，所以可以像迭代数组一样迭代它。除此之外，它的思想与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)
使用两个堆栈构造一个队列。
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());
}
}
}
我认为实现堆栈和队列的最干净的方法应该是使用一个允许从两端添加和删除的容器，然后限制其在一端的功能，这可以通过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();
