1670. 设计前中后队列

请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。

请你完成 FrontMiddleBack 类：

FrontMiddleBack() 初始化队列。
void pushFront(int val) 将 val 添加到队列的最前面。
void pushMiddle(int val) 将 val 添加到队列的正中间。
void pushBack(int val) 将 val 添加到队里的最后面。
int popFront() 将最前面的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popMiddle() 将正中间的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popBack() 将最后面的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。

请注意当有两个中间位置的时候，选择靠前面的位置进行操作。比方说：

将 6 添加到 [1, 2, 3, 4, 5] 的中间位置，结果数组为 [1, 2, 6, 3, 4, 5] 。
从 [1, 2, 3, 4, 5, 6] 的中间位置弹出元素，返回 3 ，数组变为 [1, 2, 4, 5, 6] 。

示例

输入：
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
输出：
[null, null, null, null, null, 1, 3, 4, 2, -1]

解释：
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1); // [1]
q.pushBack(2); // [1, 2]
q.pushMiddle(3); // [1, 3, 2]
q.pushMiddle(4); // [1, 4, 3, 2]
q.popFront(); // 返回 1 -> [4, 3, 2]
q.popMiddle(); // 返回 3 -> [4, 2]
q.popMiddle(); // 返回 4 -> [2]
q.popBack(); // 返回 2 -> []
q.popFront(); // 返回 -1 -> [] （队列为空）

链表实现队列

function NodeList(val, next = null) {
  this.val = val
  this.next = next
}

// 初始化
var FrontMiddleBackQueue = function() {
  this.head = new NodeList(-1)
};

// 入前队
FrontMiddleBackQueue.prototype.pushFront = function(val) {
  if(!this.head.next){
    this.head.val = val
  }else{
    let pre = this.head.next
    this.head.next = new NodeList(val,pre)
  }
};

// 入中队
FrontMiddleBackQueue.prototype.pushMiddle = function(val) {
  let slow = this.head
  let fast = this.head.next ? this.head.next.next : this.head.next

  // 取中间
  while(fast && fast.next){
    slow = slow.next
    fast = fast.next.next
  }

  let temp = slow.next
  slow.next = new NodeList(val,temp)
};

// 入后队
FrontMiddleBackQueue.prototype.pushBack = function(val) {
  let node = this.head
  while(node.next){
    node = node.next
  }
  node.next = new NodeList(val)
};

// 出前队
FrontMiddleBackQueue.prototype.popFront = function() {
  if(!this.head.next)return -1

  let temp = this.head.next
  this.head = this.head.next
  return temp.val
};

// 出中队
FrontMiddleBackQueue.prototype.popMiddle = function() {
  let slow = this.head
  let fast = this.head.next ? this.head.next.next : this.head.next

  // 取中间
  while(fast && fast.next){
    slow = slow.next
    fast = fast.next.next
  }

  let temp = slow.next

  if(temp.next){
    slow.next = slow.next.next
    return temp.val
  }else{ // 只剩两节点
    this.head = this.head.next
  }

};

// 出后队
FrontMiddleBackQueue.prototype.popBack = function() {
  // 最后一个
  if(!this.head.next){
    let temp = this.head.val
    this.head.val = null
    return temp
  }

  let slow = this.head
  let fast = this.head.next

  // 取最后
  while(fast && fast.next){
    slow = slow.next
    fast = fast.next
  }
  
  let temp = slow
  slow.next = null
  return temp.val
};

const q = new FrontMiddleBackQueue()
q.pushFront(1) // [1]
//   q.pushFront(2); // [2,1]
q.pushBack(2) // [1, 2]
q.pushMiddle(3) // [1, 3, 2]
q.pushMiddle(4) // [1, 4, 3, 2]
q.popFront() // 返回 1 -> [4, 3, 2]
q.popMiddle() // 返回 3 -> [4, 2]
q.popMiddle() // 返回 4 -> [2]
q.popBack() // 返回 2 -> []
console.log(q.popFront()) // 返回 -1 -> [] （队列为空）

console.log(q)

1670. 设计前中后队列

链表实现队列​

链表实现队列