双端队列数据结构

date
Mar 13, 2023
slug
js-two-ended-queue
status
Published
tags
JavaScript数据结构与算法
Queue
JavaScript
summary
JavaScript Two-ended Queue init
type
Post
​ 双端队列是一种允许我们同时从前端和后端添加和移除元素的特殊队列。
双端队列的一个常见应用是存储一系列的撤销操作。由于双端队列同时遵守了先进先出和后进先出原 则，可以说它是把队列和栈相结合的一种数据结构。

创建Deque类

class Deque{
    constructor(){
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
}
  • addFront(element)：该方法在双端队列前端添加新的元素。
  • addBack(element)：该方法在双端队列后端添加新的元素（实现方法和 Queue 类中的 enqueue 方法相同）
  • removeFront()：该方法会从双端队列前端移除第一个元素（实现方法和 Queue 类中的 dequeue 方法相同）。
  • removeBack()：该方法会从双端队列后端移除第一个元素（实现方法和 Stack 类中的 pop 方法一样）。
  • peekFront()：该方法返回双端队列前端的第一个元素（实现方法和 Queue 类中的 peek 方法一样）。
  • peekBack()：该方法返回双端队列后端的第一个元素（实现方法和 Stack 类中的 peek 方法一样）

向双端队列的前端添加元素

addFront(elememnt){
    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.lowestCount = 0;
        this.items[0] = element;
    }
}

添加元素会出现三种情况：

情况一：这个双端队列是空的，执行 addBack 方法。元素会被添加到双端队列的后端，在本例中也是双端队列的前端。addBack 方法已经有了增加 count 属性值的逻辑，因此我们可以复用它来避免重复编写代码。
情况二：一个或多个元素已经被从双端队列的前端移除，也就是说 lowestCount 属性会大于等于 1。将 lowestCount 属性减 1 并将新元素的值放在这个 键的位置上。例如：我们想将元素 7添加在双端队列的前端
items = { 
 1: 8, 
 2: 9 
}; 
count = 3; 
lowestCount = 1;
情况三：lowestCount 为 0。要在第一位添加一个 新元素，我们需要将所有元素后移一位来空出第一个位置。由于我们不想丢失任何已 有的值，需要从最后一位开始迭代所有的值，并为元素赋上索引值减 1 位置的值。在所有的元素 都完成移动后，第一位将是空闲状态，这样就可以用需要添加的新元素来覆盖它了。

© shallrise 2025