在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;
};
其他回答
我在实现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();
var x = 10;
var y = 11;
var Queue = new Array();
Queue.unshift(x);
Queue.unshift(y);
console.log(Queue)
// Output [11, 10]
Queue.pop()
console.log(Queue)
// Output [11]
如果你正在寻找带有一些基本操作(基于链表)的堆栈和队列数据结构的ES6 OOP实现,那么它可能是这样的:
Queue.js
import LinkedList from '../linked-list/LinkedList';
export default class Queue {
constructor() {
this.linkedList = new LinkedList();
}
isEmpty() {
return !this.linkedList.tail;
}
peek() {
if (!this.linkedList.head) {
return null;
}
return this.linkedList.head.value;
}
enqueue(value) {
this.linkedList.append(value);
}
dequeue() {
const removedHead = this.linkedList.deleteHead();
return removedHead ? removedHead.value : null;
}
toString(callback) {
return this.linkedList.toString(callback);
}
}
Stack.js
import LinkedList from '../linked-list/LinkedList';
export default class Stack {
constructor() {
this.linkedList = new LinkedList();
}
/**
* @return {boolean}
*/
isEmpty() {
return !this.linkedList.tail;
}
/**
* @return {*}
*/
peek() {
if (!this.linkedList.tail) {
return null;
}
return this.linkedList.tail.value;
}
/**
* @param {*} value
*/
push(value) {
this.linkedList.append(value);
}
/**
* @return {*}
*/
pop() {
const removedTail = this.linkedList.deleteTail();
return removedTail ? removedTail.value : null;
}
/**
* @return {*[]}
*/
toArray() {
return this.linkedList
.toArray()
.map(linkedListNode => linkedListNode.value)
.reverse();
}
/**
* @param {function} [callback]
* @return {string}
*/
toString(callback) {
return this.linkedList.toString(callback);
}
}
上面例子中用于堆栈和队列的LinkedList实现可以在GitHub上找到。
问候,
在Javascript中,栈和队列的实现如下:
堆栈:堆栈是一个容器,其中的对象是根据后进先出(LIFO)原则插入和删除的。
方法将一个或多个元素添加到数组的末尾,并返回数组的新长度。 方法从数组中删除最后一个元素并返回该元素。
队列:队列是根据先进先出(FIFO)原则插入和删除对象的容器(线性集合)。
方法将一个或多个元素添加到数组的开头。 Shift:该方法从数组中移除第一个元素。
let stack = []; stack.push(1);//[1] stack.push(2);//[1,2] stack.push(3);//[1,2,3] console.log('It was inserted 1,2,3 in stack:', ...stack); stack.pop(); //[1,2] console.log('Item 3 was removed:', ...stack); stack.pop(); //[1] console.log('Item 2 was removed:', ...stack); let queue = []; queue.push(1);//[1] queue.push(2);//[1,2] queue.push(3);//[1,2,3] console.log('It was inserted 1,2,3 in queue:', ...queue); queue.shift();// [2,3] console.log('Item 1 was removed:', ...queue); queue.shift();// [3] console.log('Item 2 was removed:', ...queue);