📬栈与🎏队列 - 🎏双端队列的JavaScript实现 - 《算法与LeetCode题解》

双端队列(deque)是一种允许同时从前端和后端添加和移除元素的特殊队列。

双端队列在现实生活中的例子有电影院、餐厅中排队的队伍等。举个例子，一个刚买了票的人如果只是还需要再问一些简单的信息，就可以直接回到队伍的头部。另外，在队伍末尾的人如果赶时间，他可以直接离开队伍。

在计算机科学中，双端队列的一个常见应用是存储一系列的撤销操作。每当用户在软件中进行了一个操作，该操作会被存在一个双端队列中（就像在一个栈里）。当用户点击撤销按钮时，该操作会被从双端队列中弹出，表示它被从后面移除了。在进行了预先定义的一定数量的操作后，最先进行的操作会被从双端队列的前端移除。由于双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。

详细内容可看：
5️⃣ 队列和双端队列
既然双端队列是一种特殊的队列，可以看到其构造函数中的部分代码和队列相同，包括相同的内部属性和以下方法：isEmpty、clear、size和toString。由于双端队列允许在两端添加和移除元素，还会有下面几个方法:

addFront(element)：该方法在双端队列前端添加新的元素。
addBack(element)：该方法在双端队列后端添加新的元素（实现方法和Queue类中的enqueue方法相同）。
removeFront()：该方法会从双端队列前端移除第一个元素（实现方法和Queue类中的dequeue方法相同）。
removeBack()：该方法会从双端队列后端移除第一个元素（实现方法和Stack类中的pop方法一样）。
peekFront()：该方法返回双端队列前端的第一个元素（实现方法和Queue类中的peek方法一样）。
peekBack()：该方法返回双端队列后端的第一个元素（实现方法和Stack类中的peek方法一样）。 ```javascript export default class Deque{ constructor() {
```
  this.items = {}
  this.count = 0
  this.lowestCount = 0
```
}
```
addFront(element) {
```
if (this.isEmpty()) {
```
this.addBack(element);
```
} else if (this.lowestCount > 0) {
```
this.lowestCount--;
this.items[this.lowestCount] = element;
```
} else {
```
for (let i = this.count; i > 0; i--) {
  this.items[i] = this.items[i - 1];
}
this.count++;
this.items[0] = element;
```
} }

addBack(element) { this.items[this.count] = element; this.count++; }

removeFront() { if (this.isEmpty()) {
```
return undefined;
```
} const result = this.items[this.lowestCount]; delete this.items[this.lowestCount]; this.lowestCount++; return result; }

removeBack() { if (this.isEmpty()) {
```
return undefined;
```
} this.count—; const result = this.items[this.count]; delete this.items[this.count]; return result; }

peekFront() { if (this.isEmpty()) {
```
return undefined;
```
} return this.items[this.lowestCount]; }

peekBack() { if (this.isEmpty()) {
```
return undefined;
```
} return this.items[this.count - 1]; }

isEmpty() { return this.size() === 0; }

clear() { this.items = {}; this.count = 0; this.lowestCount = 0; }

size() { return this.count - this.lowestCount; }

toString() { if (this.isEmpty()) {
```
return '';
```
} let objString = ${this.items[this.lowestCount]}; for (let i = this.lowestCount + 1; i < this.count; i++) {
```
objString = `${objString},${this.items[i]}`;
```
} return objString; }

} ```