在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
在我看来,内建数组对于堆栈来说是很好的。如果你想在TypeScript中使用Queue,这里有一个实现
/**
* 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 array
for (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 immediately
if (this.queue.length === 0) {
return null;
}
// store the item at the front of the queue
const item = this.queue[this.offset];
// increment the offset and remove the free space if necessary
if (++this.offset * 2 >= this.queue.length) {
this.queue = this.queue.slice(this.offset);
this.offset = 0;
}
// return the dequeued item
return 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);
}
}
这里有一个笑话测试
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();
});
希望有人觉得这有用,
欢呼,
Stu
其他回答
As many have said: native array using push and pop is fine for a stack, but using shift for taking elements from a queue means that the remaining elements need to move, which is potentially slow. The idea of using two stacks to make a queue in kevinyu's answer is a nice idea to fix it, and of course that can be done with native-array-stacks as well. (Edit: there was actually already an answer by Yuki-Dreamer that does this, albeit less compactly. I didn't notice it until now because it was unfairly downvoted.)
下面是一个使用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.length); // outputs 3
console.log(q.shift()); // outputs 8
q.push(11);
console.log(q.shift()); // outputs 9
console.log(q.shift()); // outputs 10
console.log(q.shift()); // outputs 11
console.log(q.shift()); // outputs undefined
队列实现对长度使用getter语法,使其看起来像一个属性,并对push使用rest参数语法,以允许一次推送多个内容。如果你不想这样做,你可以用push: elt => a.push(elt),替换第4行。(但是请注意,你不能用push: a.push替换它,就像我自己第一次尝试的那样,结果非常奇怪:这是因为它导致本机push方法被调用,并设置为队列对象。)
数组。
栈:
var stack = [];
//put value on top of stack
stack.push(1);
//remove value from top of stack
var value = stack.pop();
队列:
var queue = [];
//put value on end of queue
queue.push(1);
//Take first value from queue
var value = queue.shift();
或者可以使用两个数组来实现队列数据结构。
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
有点晚了,但我认为答案应该在这里。下面是一个使用稀疏数组幂的O(1)入队列和O(1)出队列的Queue实现。
JS中的稀疏数组通常被忽视,但实际上它们是一块宝石,我们应该在一些关键任务中使用它们的力量。
这是一个骨架队列实现它扩展了数组类型并在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 break console.log(q.enqueue(10)); // add 10 console.log(q.enqueue("DIO")); // add "DIO" (Last In Line cCc R.J.DIO reis cCc) console.log(q); // display q console.log(q.dequeue()); // lets get the first one in the line console.log(q.dequeue()); // lets get DIO out from the line .as-console-wrapper { max-height: 100% !important; }
那么这里是否存在潜在的内存泄漏?不,我不这么认为。JS的稀疏数组是不连续的。因此,删除的项不应该成为数组内存占用的一部分。让GC帮你完成任务。这是免费的。
一个潜在的问题是,长度属性在不断将项目放入队列时无限增长。然而,仍然可以实现一个自动刷新(冷凝)机制,一旦长度达到某个值。
编辑:
上面的代码很好,但是删除操作符仍然是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;
}
};
这是一个非常快速的队列结构,并使用私有类字段隐藏关键变量以防止窥视。
Javascript有push和pop方法,它们操作在普通的Javascript数组对象上。
关于排队,请看这里:
http://safalra.com/web-design/javascript/queues/
Queues can be implemented in JavaScript using either the push and shift methods or unshift and pop methods of the array object. Although this is a simple way to implement queues, it is very inefficient for large queues — because of the methods operate on arrays, the shift and unshift methods move every element in the array each time they are called. Queue.js is a simple and efficient queue implementation for JavaScript whose dequeue function runs in amortized constant time. As a result, for larger queues, it can be significantly faster than using arrays.