JavaScript队列本地化

Question

JavaScript队列本地化

6

我正在学习算法和数据结构。如何在JavaScript中使用队列？

我知道你可以像这样做。

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

但是使用 shift() 方法会移动所有元素，因此时间复杂度为 O(N)，而不是 Java 中的 Dequeue 时间复杂度为 O(1)。

为什么 JavaScript 原生没有队列的概念，就像 Stack(array) 一样？

我只是很好奇，请给我指点迷津。

(我自己问了这个问题，但是找不到一个合理的原因，为什么 ES8 或 ES9 不会内置具有 Dequeue O(1) 和 enqueue O(1) 的队列，而无需自己实现)

PS：对于这个愚蠢的问题，我感到抱歉，但这一直在困扰着我！

- TechnoCorner

正如你所提到的，Array 被设计为一个非常灵活的对象，你可以通过调用不同的方法来模拟数组、栈和队列操作。我认为对于这样的操作，它的时间复杂度并不是 O(N)。 - tibetty

任何 shift 或 unshift() 操作都会重新创建数组。因此，如果我没有弄错的话，它将是 O(N)。 - TechnoCorner

你怎么知道JS实现没有优化.shift()以避免重建整个数组？ - nnnnnn

先生，这只是最坏情况。几乎所有算法都有最坏情况。 - tibetty

1

@djna 是的，这就是所谓的墨菲定律， :-) - tibetty

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DoloMike · Accepted Answer

你可以使用纯净的JS来实现它。为什么它不是原生的，可能是因为效率提高几乎从来不是必要的，而数组/对象已经足够灵活。

function Queue() {
    this._oldestIndex = 1;
    this._newestIndex = 1;
    this._storage = {};
}

Queue.prototype.size = function() {
    return this._newestIndex - this._oldestIndex;
};

Queue.prototype.enqueue = function(data) {
    this._storage[this._newestIndex] = data;
    this._newestIndex++;
};

Queue.prototype.dequeue = function() {
    var oldestIndex = this._oldestIndex,
        newestIndex = this._newestIndex,
        deletedData;

    if (oldestIndex !== newestIndex) {
        deletedData = this._storage[oldestIndex];
        delete this._storage[oldestIndex];
        this._oldestIndex++;

        return deletedData;
    }
};