如何使用数组实现JavaScript队列

如何使用数组实现JavaScript队列

一、队列数据结构简介

队列是元素的有序列表，其中元素插入到队列的末尾，并从队列的前面删除。

与基于先进先出（LIFO）原理工作的堆栈不同，队列基于先进先出（FIFO）原理工作。

队列有两个主要操作，涉及插入新元素和删除现有元素。

插入操作称为enqueue，而删除操作称为dequeue。入队操作在队列的末尾插入一个元素，而出队操作从队列的前部删除一个元素。

下图说明了一个队列：

js数组中实现一个堆栈和队列的操作示例代码：

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

队列的另一个重要操作是将元素放在最前面，称为peek。与出队操作不同，窥视操作仅返回最前面的元素，而无需修改队列。

名称 队列类似于银行中的客户队列。先到的顾客将首先得到服务，而后一位的顾客将被排在队列的末尾，然后再得到服务。

在银行排队

您可以通过使用Array类型的两个方法来将数组用作队列：

使用push()方法在数组的末尾添加一个元素。此方法等效于入队操作。

使用shift()方法从数组的开头删除元素 。与出队操作相同。

让我们通过使用数组来实现JavaScript队列数据结构。

以下是队列的构造函数：

function Queue() {
    this.elements = [];
}

该Queue()构造函数使用数组来存储它的元件。

该enqueue()方法在队列末尾添加一个元素。我们使用push()数组对象的方法在队列末尾插入新元素。

Queue.prototype.enqueue = function (e) {
     this.elements.push(e);
};

该dequeue()方法从队列的开头删除一个元素。在dequeue()方法中，我们使用shift()数组的方法删除队列前面的元素。

Queue.prototype.dequeue = function () {
     return this.elements.shift();
};

该isEmpty()方法通过检查length数组的属性是否为零来检查队列是否为空。

Queue.prototype.isEmpty = function () {
    return this.elements.length == 0;
};

该peek()方法无需修改即可访问队列开头的元素。

Queue.prototype.peek = function () {
    return !this.isEmpty() ? this.elements[0] : undefined;
};

为了查询队列的长度，我们开发了length()一种方法：

Queue.prototype.length = function() {
    return this.elements.length;
}

要从Queue()构造函数创建新队列，请使用new关键字，如下所示：

let q = new Queue();

//要排队1到7之间的数字，请使用以下代码。

for (let i = 1; i <= 7; i++) {
   q.enqueue(i);
}

若要将数字放在队列的最前面，请使用peek()方法。

console.log(q.peek()); // 1

要获取队列的当前长度，请使用length()以下示例中的方法。

console.log(q.length()); // 7

要删除队列前面的元素，请使用以下dequeue()方法：

while (!q.isEmpty()) {
     console.log(q.dequeue());
}

现在，您应该对队列数据结构有了很好的了解，并且知道如何使用Array类型的push()和shift()方法在JavaScript中实现队列。