在 JavaScript 中实现堆栈和队列的最佳方法是什么？
我正在寻找调车场算法，我将需要这些数据结构。
你如何在 JavaScript 中实现堆栈和队列？
IT技术
javascript
data-structures
stack
queue
2021-01-26 00:22:52
6个回答
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
Javascript 有 push 和 pop 方法，它们对普通的 Javascript 数组对象进行操作。
对于队列，请看这里：
http://safalra.com/web-design/javascript/queues/
队列可以在 JavaScript 中使用数组对象的 push 和 shift 方法或 unshift 和 pop 方法实现。虽然这是实现队列的简单方法，但对于大队列来说效率非常低——因为这些方法对数组进行操作，每次调用时，shift 和 unshift 方法都会移动数组中的每个元素。
Queue.js 是一个简单而高效的 JavaScript 队列实现，它的出队函数在分摊常数时间内运行。因此，对于较大的队列，它可以比使用数组快得多。
数组。
堆：
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 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;
};
这是我使用链表实现的堆栈和队列：
// Linked List
function Node(data) {
this.data = data;
this.next = null;
}
// Stack implemented using LinkedList
function Stack() {
this.top = null;
}
Stack.prototype.push = function(data) {
var newNode = new Node(data);
newNode.next = this.top; //Special attention
this.top = newNode;
}
Stack.prototype.pop = function() {
if (this.top !== null) {
var topItem = this.top.data;
this.top = this.top.next;
return topItem;
}
return null;
}
Stack.prototype.print = function() {
var curr = this.top;
while (curr) {
console.log(curr.data);
curr = curr.next;
}
}
// var stack = new Stack();
// stack.push(3);
// stack.push(5);
// stack.push(7);
// stack.print();
// Queue implemented using LinkedList
function Queue() {
this.head = null;
this.tail = null;
}
Queue.prototype.enqueue = function(data) {
var newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}
Queue.prototype.dequeue = function() {
var newNode;
if (this.head !== null) {
newNode = this.head.data;
this.head = this.head.next;
}
return newNode;
}
Queue.prototype.print = function() {
var curr = this.head;
while (curr) {
console.log(curr.data);
curr = curr.next;
}
}
var queue = new Queue();
queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.print();
queue.dequeue();
queue.dequeue();
queue.print();