如何在JavaScript中实现堆栈和队列?

在JavaScript中实现堆栈和队列的最佳方法是什么?

我想做调车场算法我需要这些数据结构。

当前回答

如果你正在寻找带有一些基本操作(基于链表)的堆栈和队列数据结构的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上找到。

2018-05-14 12:14:39

其他回答

这是我的实现堆栈。

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());

2018-02-16 07:47:39

问候,

在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);

2018-12-20 16:33:02

单端队列

这是一个使用映射的队列。由于插入顺序得到了保证，所以可以像迭代数组一样迭代它。除此之外，它的思想与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)

2021-08-03 17:46:42

如果有人需要它，你可以使用这个NPM包https://www.npmjs.com/package/data-structures-typescript，它有一个队列和堆栈，它支持javascript和typescript，它是通用的，所以你可以用你自己的值类型;)

2022-07-26 13:17:29