在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
如果你想创建自己的数据结构,你可以创建自己的:
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中的常规数组结构是一个堆栈(先入后出),也可以用作队列(先入先出),这取决于你所做的调用。
检查这个链接,看看如何让一个数组像一个队列:
队列
或者可以使用两个数组来实现队列数据结构。
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
你可以使用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)执行排队和出队列,并且没有浪费内存。
Dmitri Pavlutin在他的博客https://dmitripavlutin.com/javascript-queue/上有一个很好的入门代码
它只遗漏了一个长度为0的检查,这是很容易添加的。
这个解决方案的最大和唯一的问题是不断增长的索引可能会在某一点上达到一些数量限制,如果队列运行很长时间和/或高速(我的意图是处理音频=高速)。
这个问题没有完美的解决方案……最简单的方法是在队列为空时将索引重置为0。
最后,我添加了一个重构方法,它将所有索引移回开始,以在队列永远不为空的情况下使用。
性能无疑是更好的(以毫秒为单位的时间,排队10000个号码然后退出它们):
class QueueObject {
constructor () {
this.data = {}
this.head = 0
this.tail = 0
this.length = 0
}
enqueue (value) {
this.data[this.tail++] = value
this.length++
}
dequeue () {
let value
if (this.length > 0) {
this.length--
value = this.data[this.head]
delete this.data[this.head++]
} else {
this.head = 0
this.tail = 0
value = 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.length
this.head = 0
}
}
}
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技巧”