在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
你可以基于这个概念使用你自己的自定义类,这里是你可以用来做这些事情的代码片段
/*
* 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();
其他回答
问候,
在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);
var stack = [];
stack.push(2); // stack is now [2]
stack.push(5); // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i); // displays 5
var queue = [];
queue.push(2); // queue is now [2]
queue.push(5); // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i); // displays 2
摘自“9个你可能不知道的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]
如果你正在寻找带有一些基本操作(基于链表)的堆栈和队列数据结构的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上找到。
如果你想创建自己的数据结构,你可以创建自己的:
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;
};