在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
下面是一个相当简单的队列实现,有两个目标:
与array.shift()不同,您知道这个出队列方法需要常数时间(O(1))。 为了提高速度,这种方法使用的分配比链表方法少得多。
堆栈实现只共享第二个目标。
// Queue
function Queue() {
this.q = new Array(5);
this.first = 0;
this.size = 0;
}
Queue.prototype.enqueue = function(a) {
var other;
if (this.size == this.q.length) {
other = new Array(this.size*2);
for (var i = 0; i < this.size; i++) {
other[i] = this.q[(this.first+i)%this.size];
}
this.first = 0;
this.q = other;
}
this.q[(this.first+this.size)%this.q.length] = a;
this.size++;
};
Queue.prototype.dequeue = function() {
if (this.size == 0) return undefined;
this.size--;
var ret = this.q[this.first];
this.first = (this.first+1)%this.q.length;
return ret;
};
Queue.prototype.peek = function() { return this.size > 0 ? this.q[this.first] : undefined; };
Queue.prototype.isEmpty = function() { return this.size == 0; };
// Stack
function Stack() {
this.s = new Array(5);
this.size = 0;
}
Stack.prototype.push = function(a) {
var other;
if (this.size == this.s.length) {
other = new Array(this.s.length*2);
for (var i = 0; i < this.s.length; i++) other[i] = this.s[i];
this.s = other;
}
this.s[this.size++] = a;
};
Stack.prototype.pop = function() {
if (this.size == 0) return undefined;
return this.s[--this.size];
};
Stack.prototype.peek = function() { return this.size > 0 ? this.s[this.size-1] : undefined; };
其他回答
我在实现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();
数组。
栈:
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();
你可以基于这个概念使用你自己的自定义类,这里是你可以用来做这些事情的代码片段
/*
* Stack implementation in JavaScript
*/
function Stack() {
this.top = null;
this.count = 0;
this.getCount = function() {
return this.count;
}
this.getTop = function() {
return this.top;
}
this.push = function(data) {
var node = {
data: data,
next: null
}
node.next = this.top;
this.top = node;
this.count++;
}
this.peek = function() {
if (this.top === null) {
return null;
} else {
return this.top.data;
}
}
this.pop = function() {
if (this.top === null) {
return null;
} else {
var out = this.top;
this.top = this.top.next;
if (this.count > 0) {
this.count--;
}
return out.data;
}
}
this.displayAll = function() {
if (this.top === null) {
return null;
} else {
var arr = new Array();
var current = this.top;
//console.log(current);
for (var i = 0; i < this.count; i++) {
arr[i] = current.data;
current = current.next;
}
return arr;
}
}
}
要检查这一点,请使用控制台,并逐一尝试这些行。
>> var st = new Stack();
>> st.push("BP");
>> st.push("NK");
>> st.getTop();
>> st.getCount();
>> st.displayAll();
>> st.pop();
>> st.displayAll();
>> st.getTop();
>> st.peek();
在我看来,内建数组对于堆栈来说是很好的。如果你想在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
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.