在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
下面是我使用链表实现的堆栈和队列:
// 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();
其他回答
没有数组(年代)
//Javascript stack linked list data structure (no array)
function node(value, noderef) {
this.value = value;
this.next = noderef;
}
function stack() {
this.push = function (value) {
this.next = this.first;
this.first = new node(value, this.next);
}
this.pop = function () {
var popvalue = this.first.value;
this.first = this.first.next;
return popvalue;
}
this.hasnext = function () {
return this.next != undefined;
}
this.isempty = function () {
return this.first == undefined;
}
}
//Javascript stack linked list data structure (no array)
function node(value, noderef) {
this.value = value;
this.next = undefined;
}
function queue() {
this.enqueue = function (value) {
this.oldlast = this.last;
this.last = new node(value);
if (this.isempty())
this.first = this.last;
else
this.oldlast.next = this.last;
}
this.dequeue = function () {
var queuvalue = this.first.value;
this.first = this.first.next;
return queuvalue;
}
this.hasnext = function () {
return this.first.next != undefined;
}
this.isempty = function () {
return this.first == undefined;
}
}
很抱歉碰到这个话题，但我滚动了许多答案，没有看到任何基于对象的队列的实现，它可以用O(1)执行排队和出队列，并且没有浪费内存。
Dmitri Pavlutin在他的博客https://dmitripavlutin.com/javascript-queue/上有一个很好的入门代码
它只遗漏了一个长度为0的检查，这是很容易添加的。
这个解决方案的最大和唯一的问题是不断增长的索引可能会在某一点上达到一些数量限制，如果队列运行很长时间和/或高速(我的意图是处理音频=高速)。
这个问题没有完美的解决方案……最简单的方法是在队列为空时将索引重置为0。
最后，我添加了一个重构方法，它将所有索引移回开始，以在队列永远不为空的情况下使用。
性能无疑是更好的(以毫秒为单位的时间，排队10000个号码然后退出它们):
class QueueObject {
constructor () {
this.data = {}
this.head = 0
this.tail = 0
this.length = 0
}
enqueue (value) {
this.data[this.tail++] = value
this.length++
}
dequeue () {
let value
if (this.length > 0) {
this.length--
value = this.data[this.head]
delete this.data[this.head++]
} else {
this.head = 0
this.tail = 0
value = null
}
return value
}
refactor () {
if (this.head > 0) {
for (let i = this.head; i < this.tail; i++) {
this.data[i - this.head] = this.data[i]
delete this.data[i]
}
this.tail = this.length
this.head = 0
}
}
}
有很多方法可以在Javascript中实现堆栈和队列。上面的大多数答案都是非常肤浅的实现，我将尝试实现一些更可读(使用es6的新语法特性)和更健壮的东西。
下面是堆栈实现:
class Stack {
constructor(...items){
this._items = []
if(items.length>0)
items.forEach(item => this._items.push(item) )
}
push(...items){
//push item to the stack
items.forEach(item => this._items.push(item) )
return this._items;
}
pop(count=0){
//pull out the topmost item (last item) from stack
if(count===0)
return this._items.pop()
else
return this._items.splice( -count, count )
}
peek(){
// see what's the last item in stack
return this._items[this._items.length-1]
}
size(){
//no. of items in stack
return this._items.length
}
isEmpty(){
// return whether the stack is empty or not
return this._items.length==0
}
toArray(){
return this._items;
}
}
下面是如何使用堆栈:
let my_stack = new Stack(1,24,4);
// [1, 24, 4]
my_stack.push(23)
//[1, 24, 4, 23]
my_stack.push(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_stack.pop();
//[1, 24, 4, 23, 1, 2]
my_stack.pop(3)
//[1, 24, 4]
my_stack.isEmpty()
// false
my_stack.size();
//3
如果您想查看关于此实现的详细描述以及如何进一步改进，请阅读这里:http://jschap.com/data-structures-in-javascript-stack/
下面是es6中队列实现的代码:
class Queue{
constructor(...items){
//initialize the items in queue
this._items = []
// enqueuing the items passed to the constructor
this.enqueue(...items)
}
enqueue(...items){
//push items into the queue
items.forEach( item => this._items.push(item) )
return this._items;
}
dequeue(count=1){
//pull out the first item from the queue
this._items.splice(0,count);
return this._items;
}
peek(){
//peek at the first item from the queue
return this._items[0]
}
size(){
//get the length of queue
return this._items.length
}
isEmpty(){
//find whether the queue is empty or no
return this._items.length===0
}
}
下面是如何使用这个实现:
let my_queue = new Queue(1,24,4);
// [1, 24, 4]
my_queue.enqueue(23)
//[1, 24, 4, 23]
my_queue.enqueue(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_queue.dequeue();
//[24, 4, 23, 1, 2, 342]
my_queue.dequeue(3)
//[1, 2, 342]
my_queue.isEmpty()
// false
my_queue.size();
//3
要完整地了解如何实现这些数据结构以及如何进一步改进这些数据结构，您可能需要阅读jschap.com上的“在javascript中处理数据结构”系列。这是队列的链接——http://jschap.com/playing-data-structures-javascript-queues/
单端队列
这是一个使用映射的队列。由于插入顺序得到了保证，所以可以像迭代数组一样迭代它。除此之外，它的思想与Queue.js非常相似。
我做了一些简单的测试，但还没有进行广泛的测试。我还添加了一些我认为很好的功能(通过数组构造)或易于实现(例如last()和first())。
它背后的简单版本/直觉如下:
class Queue {
constructor() {
this.offset = 0
this.data = new Map()
}
enqueue(item) {
const current = this.offset + this.length()
this.data.set(current, item)
}
dequeue() {
if (this.length() > 0) {
this.data.delete(this.offset)
this.offset += 1
}
}
first() {
return this.data.get(this.offset)
}
last() {
return this.data.get(this.offset + this.length() - 1)
}
length() {
return this.data.size
}
}
简单版本的问题是，当内存索引超过9千万亿(Number.MAX_SAFE_INTEGER的值)时，需要重新映射内存。此外，我认为它可能很好有数组构造，它很高兴看到值正在进入队列和退出队列返回。可以通过编写以下代码来解释这一点:
class Queue {
constructor() {
this.offset = 0
this.data = new Map()
if (arguments.length === 1) this._initializeFromArray(arguments[0])
}
enqueue(item) {
const current = this.offset + this.length()
this.data.set(current, item)
let result = this.data.get(current)
this._remapDataIfMaxMemoryViolation(current, Number.MAX_SAFE_INTEGER)
return result
}
dequeue() {
let result = undefined
if (this.length() > 0) {
result = this.data.get(this.offset)
this.data.delete(this.offset)
this.offset += 1
}
if (this.length() === 0) this.offset = 0
return result
}
first() {
return this.data.get(this.offset)
}
last() {
return this.data.get(this.offset + this.length() - 1)
}
length() {
return this.data.size
}
_remapDataIfMaxMemoryViolation(current, threshhold) {
if (current+1 === threshhold) {
const length = this.length()
this.offset = 0
for (const [key, value] of this.data) {
this.data.set(this.offset, value)
this.data.delete(key, value)
this.offset += 1
if (this.offset === length) break
}
}
}
_initializeFromArray(array) {
for (const value of array) {
this.data.set(this.offset, value)
this.offset += 1
}
}
}
我在Chrome开发控制台进行了一些测试，对完整版本进行了以下调用。
l = console.log // I'm lazy with typing
q = new Queue()
l('enqueue', q.enqueue(1))
l('enqueue', q.enqueue(2))
l('enqueue', q.enqueue(3))
l('enqueue', q.enqueue("hello"))
l('enqueue', q.enqueue("monkey"))
l('show 5 elements: ', q.data)
l('length', q.length())
l('first', q.first())
l('last', q.last())
l('dequeue', q.dequeue())
l('dequeue', q.dequeue())
l('show 3 elements', q.data)
q._remapDataIfMaxMemoryViolation(q.length()+q.offset-1, 5)
l('show 3 remapped elements', q.data)
l(queue = new Queue([3,4,5,6,7,8,9]))
l(queue.data)
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技巧”
