JavaScript从零实现队列数据结构

"JavaScript实现队列的两种方法：基于数组和基于对象" 在JavaScript中，队列是一种先进先出（FIFO，First In First Out）的数据结构，它遵循特定的规则，即新元素添加到队列的尾部，而移除元素则从队列的头部开始。下面将详细介绍如何使用JavaScript实现队列。 ### 基于数组的实现 ```javaScript class Queue { constructor() { this.items = []; // 利用数组存储队内元素 } // 向队列尾部添加一个（或多个）新的项 enqueue(element) { this.items.push(element); } // 移除队列的第一项（即排在队列最前面的项）并返回被移除的元素 dequeue() { return this.items.shift(); } // 返回队列中第一个元素——最先被添加，也将是最先被移除的元素 peek() { return this.items[0]; } // 如果队列中不包含任何元素，返回true，否则返回false isEmpty() { return this.items.length === 0; } // 移除队列里的所有元素 clear() { this.items = []; } // 返回队列包含的元素个数，与数组的length属性类似 size() { return this.items.length; } } const queue = new Queue(); console.log(queue.isEmpty()); // true queue.enqueue("a"); queue.enqueue("b"); console.log(queue.peek()); // a queue.enqueue("c"); console.log(queue.size()); // 3 console.log(queue.isEmpty()); // false queue.enqueue("d"); queue.dequeue(); queue.dequeue(); console.log(queue.size()); // 2 ``` ### 基于对象的实现 在基于对象的实现中，我们使用一个对象来存储元素，并通过一个`count`变量来追踪元素的顺序。 ```javaScript class Queue { constructor() { this.count = 0; this.items = {}; // 使用对象存储元素 this.lowestCount = 0; // 追踪第一个元素 } enqueue(element) { this.items[this.count] = element; this.count++; } dequeue() { if (this.isEmpty()) return undefined; const removedElement = this.items[this.lowestCount]; delete this.items[this.lowestCount]; this.lowestCount++; return removedElement; } peek() { return this.isEmpty() ? undefined : this.items[this.lowestCount]; } isEmpty() { return this.count - this.lowestCount === 0; } clear() { this.count = 0; this.lowestCount = 0; this.items = {}; } size() { return this.count - this.lowestCount; } } const queue = new Queue(); // 示例代码... ``` 在这两种实现中，`enqueue`方法用于向队列尾部添加元素，`dequeue`方法用于移除并返回队列头部的元素，`peek`方法用于查看但不移除队列头部的元素，`isEmpty`方法检查队列是否为空，`clear`方法清空队列，而`size`方法返回队列中的元素数量。基于对象的实现更灵活，因为它允许存储非数字键，但可能会有额外的内存开销，因为对象需要维护原型链和属性引用。而基于数组的实现则更加简单且高效，适用于大多数情况。