在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
Create a pair of classes that provide the various methods that each of these data structures has (push, pop, peek, etc). Now implement the methods. If you're familiar with the concepts behind stack/queue, this should be pretty straightforward. You can implement the stack with an array, and a queue with a linked list, although there are certainly other ways to go about it. Javascript will make this easy, because it is weakly typed, so you don't even have to worry about generic types, which you'd have to do if you were implementing it in Java or C#.
其他回答
使用两个堆栈构造一个队列。
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 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;
};
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技巧”
数组是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
};
}
使用链表实现的队列比这种基于映射的方法更有效,使用循环缓冲区实现的队列比这种基于映射的方法更有效,但这两种数据结构的实现更复杂(特别是循环缓冲区数据结构)。
你可以使用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