leetcode1670-设计前中后队列（来看看链表怎么实现的）

开启leetcode刷题系列。大佬云：“刷算法就像做数学题，首先要学定义，然后记住公式，最后利用公式和总结的套路去做题“。

我也是个算法小菜鸡，但是算法对于我们程序员来说确实很重要。写文章主要是为了输出，把我刷题的思路记录下来也可以更方便的复盘。当然也希望我的思路对你们也有所帮助。下面开始行动吧！虽然不知道能不能坚持住，先动手再说吧，感兴趣的同学可以联系我哦！

设计前中后队列

前中后队列是什么意思呢？也就是在前，中，后三个位置的 push 和 pop 操作的。

那我们的思路是什么呢？对于一个队列，在第一个位置新增或删除一个元素，在最后一位新增或删除一个元素，在最中间的位置新增或删除一个元素。

那我们需要用到两个循环双端队列，也就是从队列的中间截断，前面一个循环双端队列，后面一个循环双端队列。这样就可以解决中间位置的push和pop的操作了。

既然说用链表实现，那我们就得设计链表的节点咯

设计链表节点

class Node {
  constructor(val) {
    this.val = val;
    this.pre = null; // 该节点的前一个节点
    this.next = null; //  该节点的下一个节点
  }

  //   向前插入一个节点
  insert_pre(p) {
    p.next = this;
    p.pre = this.pre;
    this.pre && (this.pre.next = p);
    this.pre = p;
  }

  //   向后插入一个节点
  insert_next(p) {
    p.pre = this;
    p.next = this.next;
    this.next && (this.next.pre = p);
    this.next = p;
  }

  //  删除这个节点
  erase() {
    this.next && (this.next.pre = this.pre);
    this.pre && (this.pre.next = this.next);
  }
}

设计的节点中有pre表示前一个节点，next表示后一个节点。insert_pre表示向前插入一个节点，我们用图来解释下insert_pre的意思

需要在节点3前面插入一个节点p， 节点p的next则指向了当前节点（节点3），节点p的pre则指向了当前节点的pre节点(节点1），那么此时节点1的next节点就不是节点3了，而是节点p。这样就完成了操作。我们也可以用同样的思路去理解insert_next。erase表示删除这个节点，那么当前要删除的节点的下一个节点的pre则就指向了当前节点的上一个节点，当前要删除节点的上一个节点的next则就指向了当前节点的下一个节点。

设计循环双端队列

我们上一篇也讲述了设计循环双端队列,不过是用数组，下面我们用链表实现

class Dequeue {
  constructor() {
    this.cnt = 0;
    this.head = new Node(-1);
    this.tail = new Node(-1);
    this.head.next = this.tail;
    this.tail.pre = this.head;
  }

  // 从队尾插入
  push_Back(val) {
    this.tail.insert_pre(new Node(val));
    this.cnt++;
  }
  // 从队首插入
  push_front(val) {
    this.head.insert_next(new Node(val));
    this.cnt++;
  }

  // 从队尾弹出
  pop_back() {
    let ret = this.tail.pre.val;
    if (this.cnt) {
      this.tail.pre.erase();
      this.cnt--;
    }
    return ret;
  }

  // 从队首弹出
  pop_front() {
    let ret = this.head.next.val;
    if (this.cnt) {
      this.head.next.erase();
      this.cnt--;
    }
    return ret;
  }

  // 获取队首节点
  getFront() {
    return this.head.next.val;
  }

  // 获取队尾节点
  getRear() {
    return this.tail.pre.val;
  }

  // 队列长度
  size() {
    return this.cnt;
  }
}

在初始化的时候，我们需要一个cnt表示当前队列（也可以说成是链表）的数量，head表示虚拟头节点，tail表示虚拟尾节点。让head的下一个节点指向tail,tail的上一个节点指向head。

push_Back表示从队尾插入一个节点，其实就是在尾部节点前面插入一个节点。

push_front表示从队首插入一个节点，其实就是在头部节点后面插入一个节点。

pop_back表示从尾部删除一个节点，其实就是删除尾部节点的前一个节点

pop_front表示从队首删除一个节点，其实就是删除头部节点的后一个节点

getFront表示获取队首节点，其实就是头部节点的后一个节点

getRear表示获取队尾节点，其实就是尾部接节前一个节点

我要是会动画就好了，这样一点都不炫😂 队列已经准备好，下面给我开始搞~~~

设计前中后队列

FrontMiddleBackQueue

var FrontMiddleBackQueue = function () {
  this.q1 = new Dequeue();
  this.q2 = new Dequeue();
};

首先需要初始化，我们只需要初始化两个循环队列就好。

maintain

FrontMiddleBackQueue.prototype.maintain = function () {
  if (this.q2.size() > this.q1.size()) {
    this.q1.push_Back(this.q2.pop_front());
  } else if (this.q1.size() === this.q2.size() + 2) {
    this.q2.push_front(this.q1.pop_back());
  }
};

我们这里增加了一个方法maintain，这个方法的作用就是每次操作队列的时候，都通过调用这个方法来保证q1和q2的均衡。当队列的数量是偶数的时候，q1和q2平分，当队列的数量是奇数的时候，q1的数量比q2的数量多一个。如果q2的数量比q1的数量多，则将q2的队首节点插入到q1的队尾节点。如果q1的数量比q2的数量多两个，则将q1的队尾节点插入到q2的队首节点。

pushFront

将 val 添加到队列的 最前面

FrontMiddleBackQueue.prototype.pushFront = function (val) {
  this.q1.push_front(val);
  this.maintain();
};

其实就是将val添加到q1的队首。然后执行maintian更新q1,q2的数量。

pushMiddle

将 val 添加到队列的 正中间 。

FrontMiddleBackQueue.prototype.pushMiddle = function (val) {
  if (this.q1.size() === this.q2.size() + 1) {
    this.q2.push_front(this.q1.pop_back());
  }
  this.q1.push_Back(val);
  this.maintain();
};

如果q1的数量比q2的数量多一个，那么需要将q1的最后一个节点插入到q2的第一个节点，然后再向q1的末尾插入val,这样才可以保证q1和q2数量的均衡。如果q1的数量不比q2的数量多一个，则直接向q1的末尾插入val,然后执行maintian更新q1,q2的数量。

pushBack

将 val 添加到队里的 最后面 。

FrontMiddleBackQueue.prototype.pushBack = function (val) {
  this.q2.push_Back(val);
  this.maintain();
};

这里就直接向q2的末尾插入val,然后执行maintian更新q1,q2的数量。

popFront

将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。

FrontMiddleBackQueue.prototype.popFront = function () {
  let ret = this.q1.pop_front();
  this.maintain();
  return ret;
};

这里直接删除q1的队首元素即可。如果此时队列为空了，ret对应的则是head.val的-1,这也是为什么把虚拟头节点默认赋值为-1。然后执行maintian更新q1,q2的数量。

popMiddle

将 正中间 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。

FrontMiddleBackQueue.prototype.popMiddle = function () {
  let ret = this.q1.pop_back();
  this.maintain();
  return ret;
};

直接删除q1的队尾元素即可。如果此时队列为空了，ret对应的则是tail.val的-1,这也是为什么把虚拟尾节点默认赋值为-1。然后执行maintian更新q1,q2的数量。

popBack

将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。

FrontMiddleBackQueue.prototype.popBack = function () {
  let ret = this.q2.size() ? this.q2.pop_back() : this.q1.pop_back();
  this.maintain();
  return ret;
};

首先判断q2中是否还有元素，如果有则直接删除最后一个元素，如果没有，则删除q1的最后一个元素。然后执行maintian更新q1,q2的数量。

总结

如果想要种队列中push和pop,在需要两个循环双端队列，然后链表实现循环双端队列。其实重点在于封装，封装好了之后，实现就简单了许多。

如果大家想一起和我讨论算法可以加我wx:yoyomdd,一起学习一起进步！！！