JavaScript 队列本机

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中的Dequeue，时间复杂度是O(1)

为什么 JavaScript 本身没有像 Stack（数组）那样的队列概念？

我只是好奇而已。请赐教。

（我问自己这个问题，但找不到 ES8 或 ES9 内置 Dequeue O(1) 和 enqueue O(1) 队列而无需自己实现的有效原因）

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

Answer 1

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