JavaScript 队列 native

Question

我正在学习算法和 DS。如何在 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 中的出队 O(1)

为什么JavaScript没有像Stack(array)一样原生有Queue的概念？

我只是好奇。请赐教。

(我问过自己这个问题，但找不到合理的理由说明为什么 ES8 或 ES9 会使用出队 O(1) 和入队 O(1) 内置队列，而无需自己实现)

PS:很抱歉问了个愚蠢的问题，但这一直让我的大脑发痒!

Answer 1

您可以在普通 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;
    }
};