在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
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]
其他回答
数组。
栈:
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();
下面是一个队列的链表版本,它也包括最后一个节点,这是@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;
};
数组是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
};
}
使用链表实现的队列比这种基于映射的方法更有效,使用循环缓冲区实现的队列比这种基于映射的方法更有效,但这两种数据结构的实现更复杂(特别是循环缓冲区数据结构)。
这是我的实现堆栈。
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());