双端队列 double-end queue 是一种允许我们同时从前端和后端添加和移除的元素的特殊队列。
双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。

双端队列的方法

  • addFront(element) 在前端添加新元素
  • addBlack(element) 在后端添加新元素
  • removeFront() 从前端移除第一个元素
  • removeBack() 从后端移除第一个元素
  • peekFront() 返回前端的第一个元素
  • peekBack() 返回后端的第一个元素
  • isEmpty() 是否空双端队列
  • clear() 清空双端队列

  • size() 返回元素个数

    实现

    1. class deque {
    2. constructor() {
    3.   this.count = 0;
    4.   this.lowestCount = 0;
    5.   this.items = {};
    6. }
    8. addFront(element) {
    9.   if (this.isEmpty()) {
    10.     this.addBack(element);
    11.   } else if (this.lowestCount > 0) {
    12.     this.lowestCount--;
    13.     this.items[this.lowestCount] = element;
    14.   } else {
    15.     for (let i = this.count; i > 0; i--) {
    16.       this.items[i] = this.items[i - 1];
    17.     }
    18.     this.count++;
    19.     this.lowestCount = 0;
    20.     this.items[0] = element;
    21.   }
    22. }
    23. addBack(element) {
    24.   this.items[this.count] = element;
    25.   this.count++;
    26. }
    28. removeFront() {
    29.   if (this.isEmpty) {
    30.     return undefined;
    31.   }
    32.   const result = this.items[this.lowestCount];
    33.   delete this.items[this.lowestCount];
    34.   this.lowestCount++;
    35.   return result;
    36. }
    38. removeBack() {
    39.   if (this.isEmpty) {
    40.     return undefined;
    41.   }
    42.   this.count--;
    43.   const result = this.items[this.count];
    44.   delete this.items[this.count];
    45.   return result;
    46. }
    48. peekFront() {
    49.   if (this.isEmpty) {
    50.     return undefined;
    51.   }
    52.   return this.items[this.lowestCount];
    53. }
    55. peekBack() {
    56.   if (this.isEmpty) {
    57.     return undefined;
    58.   }
    59.   return this.items[this.count - 1];
    60. }
    62. isEmpty() {
    63.   return this.size() === 0;
    64. }
    66. size() {
    67.   return this.count - this.lowestCount;
    68. }
    70. clear() {
    71.   this.items = {};
    72.   this.count = 0;
    73.   this.lowestCount = 0;
    74. }
    76. toString() {
    77.   if (this.isEmpty()) {
    78.     return '';
    79.   }
    80.   let objString = `${this.items[this.lowestCount]}`;
    81.   for (let i = this.lowestCount + 1; i < this.count; i++) {
    82.     objString = `${objString},${this.items[i]}`;
    83.   }
    84.   return objString;
    85. }
    86. }