在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
这是我的实现堆栈。
function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
this.length = length;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function peek() {
return this.dataStore[this.top-1];
}
function pop() {
return this.dataStore[--this.top];
}
function clear() {
this.top = 0;
}
function length() {
return this.top;
}
var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());
console.log(s.peek());
其他回答
我在实现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();
下面是一个队列的链表版本,它也包括最后一个节点,这是@perkins建议的,也是最合适的。
// QUEUE Object Definition
var Queue = function() {
this.first = null;
this.last = 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){ // for empty list first and last are the same
this.first = node;
this.last = node;
} else { // otherwise we stick it on the end
this.last.next=node;
this.last=node;
}
this.size += 1;
return node;
};
Queue.prototype.dequeue = function() {
if (!this.first) //check for empty list
return null;
temp = this.first; // grab top of list
if (this.first==this.last) {
this.last=null; // when we need to pop the last one
}
this.first = this.first.next; // move top of list down
this.size -= 1;
return temp;
};
或者可以使用两个数组来实现队列数据结构。
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
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#.
如果你想创建自己的数据结构,你可以创建自己的:
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;
};