1. 队列简介
我们已经学习了栈。队列和栈非常类似，但是使用了与后进先出不同的原则。你将在本章学习这些内容。我们同样要学习双端队列的工作原理。双端队列是一种将栈的原则和队列的原则混合在一起的数据结构。
队列是遵循 先进先出(FIFO) 原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。
在现实中，最常见的队列的例子就是排队。在电影院、自助餐厅、杂货店收银台，我们都会排队。排在第一位的人会先接受服务。
在计算机科学中，一个常见的例子就是打印队列。比如说我们需要打印五份文档。我们会打开每个文档，然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文档会首先被打印，以此类推，直到打印完所有文档。
1.1. 实现
const Queue = (() => { const store = new WeakMap(); class Queue { constructor() { store.set(this, { _items: [] }); } // 只读 队列大小 get size() { return store.get(this)._items.length; } // 只读 是否为空 get isEmpty() { return this.size === 0; } // 进入队列 enqueue(ele) { store.get(this)._items.push(ele); return this.size; } // 退出队列 dequeue() { return store.get(this)._items.shift(); } // 返回队列第 1 个元素 peek() { return store.get(this)._items[0]; } // 默认迭代器 用于展示所有元素 [Symbol.iterator]() { let i = 0; return { next: () => ({ value: store.get(this)._items[i], done: i++ === this.size }), [Symbol.iterator]() { return this; }, }; } // 清空所有元素 clear() { store.get(this)._items = []; } } return Queue; })();
1.2. 使用
const queue = new Queue(); queue.size = 2; console.log(queue.size); // -> 0 console.log(queue); // -> Queue {} console.log(queue.enqueue('apple')); // -> 1 console.log(queue.enqueue('orange')); // -> 2 console.log(queue.enqueue('pear')); // -> 3 console.log(...queue); // -> 'apple' 'orange' 'pear' console.log(queue.dequeue()); // -> 'apple' console.log(queue.peek()); // -> 'orange' console.log(queue.size); // -> 2 queue.clear(); console.log(queue.isEmpty); // -> true console.log(queue.peek()); // -> undefined
2. 双端队列
双端队列(double-ended queue) 是一种允许我们同时从前端和后端添加和移除元素的特殊队列。
双端队列在现实生活中的例子有电影院、餐厅中排队的队伍等。举个例子，一个刚买了票的人如果只是还需要再问一些简单的信息，就可以直接回到队伍的头部。另外，在队伍末尾的人如果赶时间，他可以直接离开队伍。
在计算机科学中，双端队列的一个常见应用是存储一系列的撤销操作。每当用户在软件中进行了一个操作，该操作会被存在一个双端队列中（就像在一个栈里）。当用户点击撤销按钮时，该操作会被从双端队列中弹出，表示它被从后面移除了。在进行了预先定义的一定数量的操作后，最先进行的操作会被从双端队列的前端移除。由于双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。
2.1. 实现
const Dequeue = (() => { const store = new WeakMap(); class Dequeue { constructor() { store.set(this, { _items: [] }); } // 只读 元素数量 get size() { return store.get(this)._items.length; } // 只读 是否为空 get isEmpty() { return this.size === 0; } // 在前面添加元素 addFront(ele) { store.get(this)._items.unshift(ele); return this.size; } // 在前面移除元素 removeFront() { return store.get(this)._items.shift(); } // 在后面添加元素 addBack(ele) { store.get(this)._items.push(ele); return this.size; } // 在后面移除元素 removeBack() { return store.get(this)._items.pop(); } // 返回第1个元素 peekFront() { return store.get(this)._items[0]; } // 返回最后一个元素 peekBack() { return store.get(this)._items[this.size - 1]; } // 默认迭代器 展示所有元素 [Symbol.iterator]() { let i = 0; return { next: () => ({ value: store.get(this)._items[i], done: i++ === this.size }), [Symbol.iterator]() { return this; }, }; } // 清空所有元素 clear() { store.get(this)._items = []; } } return Dequeue; })();
2.2. 使用
const dequeue = new Dequeue(); dequeue.size = 2; console.log(dequeue.size); // -> 0 console.log(dequeue.addBack('orange')); // -> 1 console.log(dequeue.addBack('pear')); // -> 2 console.log(dequeue.addFront('apple')); // -> 3 console.log(...dequeue); // -> 'apple' 'orange' 'pear' console.log(dequeue.peekFront()); // -> 'apple' console.log(dequeue.peekBack()); // -> 'pear' console.log(dequeue.removeBack()); // -> 'pear' console.log(dequeue.removeFront()); // -> 'apple' dequeue.clear(); console.log(dequeue.size); // -> 0 console.log(dequeue); // -> Dequeue {}
3.优先队列
在一般情况下，从队列中删除的元素，一定是率先入队的元素。但是也有一些使用队列的
应用，在删除元素时不必遵守先进先出的约定。这种应用，需要使用一个叫做优先队列的
数据结构来进行模拟。
从优先队列中删除元素时，需要考虑优先权的限制。比如医院急诊科（Emergency Department）的候诊室，就是一个采取优先队列的例子。当病人进入候诊室时，分诊护士会评估患者病情的严重程度，然后给一个优先级代码。高优先级的患者先于低优先级的患者就医，同样优先级的患者按照先来先服务的顺序就医。
3.1实现
const PriorityQueue = (() => { const store = new WeakMap(); // 优先队列内部的元素类 class QueueElement { constructor(element, priority) { this.element = element; this.priority = priority; } } class PriorityQueue { constructor() { store.set(this, { _items: [] }); } // 只读 队列大小 get size() { return store.get(this)._items.length; } // 只读 是否为空 get isEmpty() { return this.size === 0; } // enqueue(element, priority) 入队，将元素按优先级加入到队列中 // 重写 enqueue() enqueue(element, priority) { // 根据传入的元素，创建 QueueElement 对象 const queueElement = new QueueElement(element, priority); // 判断队列是否为空 if (this.isEmpty) { // 如果为空，不用判断优先级，直接添加 store.get(this)._items.push(queueElement); } else { // 定义一个变量记录是否成功添加了新元素 let added = false; for (let i = 0; i < this.size; i++) { // 让新插入的元素进行优先级比较，priority 值越小，优先级越大 if (queueElement.priority < store.get(this)._items[i].priority) { // 在指定的位置插入元素 store.get(this)._items.splice(i, 0, queueElement); added = true; break; } } // 如果遍历完所有元素，优先级都大于新插入的元素，就将新插入的元素插入到最后 if (!added) { store.get(this)._items.push(queueElement); } } return this.size; } // 退出队列 dequeue() { return store.get(this)._items.shift(); } // 返回队列第 1 个元素 peek() { return store.get(this)._items[0]; } // 默认迭代器 用于展示所有元素 [Symbol.iterator]() { let i = 0; return { next: () => ({ value: store.get(this)._items[i], done: i++ === this.size }), [Symbol.iterator]() { return this; }, }; } // 清空所有元素 clear() { store.get(this)._items = []; } // toString() 将队列中元素以字符串形式返回 // 重写 toString() toString() { let result = ""; for (let item of store.get(this)._items) { result += item.element + "-" + item.priority + " "; } return result; } } return PriorityQueue })()
3.2使用
const queue = new PriorityQueue(); queue.size = 2; console.log(queue.size); // -> 0 console.log(queue); // -> PriorityQueue {} console.log(queue.enqueue('apple', 2)); // -> 1 console.log(queue.enqueue('orange', 1)); // -> 2 console.log(queue.enqueue('pear', 4)); // -> 3 console.log(...queue); // -> 'apple' 'orange' 'pear' console.log(queue.dequeue()); // -> 'apple' console.log(queue.peek()); // -> 'orange' console.log(queue.size); // -> 2 queue.clear(); console.log(queue.isEmpty); // -> true console.log(queue.peek()); // -> undefined
