1670.设计前中后队列

链接：1670.设计前中后队列
难度：Medium
标签：设计、队列、数组、链表、数据流
简介：请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。

题解 1 - python

• 编辑时间：2023-11-28
• 执行用时：68ms
• 内存消耗：16.81MB
• 编程语言：python
• 解法介绍：两个双端队列1670. 设计前中后队列。

class FrontMiddleBackQueue:
    def __init__(self):
        self.len = 0
        self.q1 = deque()
        self.q2 = deque()
    def pushFront(self, val: int) -> None:
        self.q1.appendleft(val)
        self.after(1)
    def pushMiddle(self, val: int) -> None:
        self.q2.appendleft(val)
        self.after(1)
    def pushBack(self, val: int) -> None:
        self.q2.append(val)
        self.after(1)
    def after(self, offset: int) -> None:
        self.len += offset
        if len(self.q1) + 2 == len(self.q2): self.q1.append(self.q2.popleft())
        elif len(self.q1) == len(self.q2) + 1: self.q2.appendleft(self.q1.pop()) 
    def popFront(self) -> int:
        if self.len == 0: return -1
        val = self.q2.pop() if self.len == 1 else self.q1.popleft()
        self.after(-1)
        return val
    def popMiddle(self) -> int:
        if self.len == 0: return -1
        val = self.q1.pop() if self.len % 2 == 0 else self.q2.popleft()
        self.after(-1)
        return val
    def popBack(self) -> int:
        if self.len == 0: return -1
        val = self.q2.pop()
        self.after(-1)
        return val

题解 2 - typescript

• 编辑时间：2021-03-14
• 执行用时：144ms
• 内存消耗：45.1MB
• 编程语言：typescript
• 解法介绍：利用两个数组维护中间值。

class FrontMiddleBackQueue {
  get frontLen() {
    return this.front.length;
  }
  get backLen() {
    return this.back.length;
  }
  get len() {
    return this.frontLen + this.backLen;
  }
  private front: number[] = [];
  private back: number[] = [];
  pushFront(val: number): void {
    this.front.unshift(val);
    this.check();
  }
  pushMiddle(val: number): void {
    this.front.push(val);
    this.check();
  }
  pushBack(val: number): void {
    this.back.push(val);
    this.check();
  }
  popFront(): number {
    if (this.len === 0) return -1;
    const num = this.frontLen === 0 ? this.back.shift()! : this.front.shift()!;
    this.check();
    return num;
  }
  popMiddle(): number {
    if (this.len === 0) return -1;
    const num = this.frontLen === 0 || this.len & 1 ? this.back.shift()! : this.front.pop()!;
    this.check();
    return num;
  }
  popBack(): number {
    if (this.len === 0) return -1;
    const num = this.backLen === 0 ? this.front.pop()! : this.back.pop()!;
    this.check();
    return num;
  }
  private check() {
    if (this.frontLen > this.backLen) {
      this.back.unshift(this.front.pop()!);
    }
    if (this.backLen > this.frontLen + 1) {
      this.front.push(this.back.shift()!);
    }
  }
}

题解 3 - cpp

• 编辑时间：2022-03-03
• 执行用时：28ms
• 内存消耗：20.4MB
• 编程语言：cpp
• 解法介绍：维护两个双端队列。

class FrontMiddleBackQueue {
   public:
    deque<int> q1, q2;
    FrontMiddleBackQueue() {}
    void balance() {
        if (empty()) return;
        while (q1.size() > q2.size()) {
            q2.push_front(q1.back());
            q1.pop_back();
        }
        while (q1.size() < q2.size() - 1) {
            q1.push_back(q2.front());
            q2.pop_front();
        }
    }
    void pushFront(int val) {
        q1.push_front(val);
        balance();
    }
    void pushMiddle(int val) {
        if (q1.size() == q2.size())
            q1.push_back(val);
        else
            q2.push_front(val);
        balance();
    }
    void pushBack(int val) {
        q2.push_back(val);
        balance();
    }
    int popFront() {
        if (empty()) return -1;
        int res;
        if (q1.size()) {
            res = q1.front();
            q1.pop_front();
        } else {
            res = q2.front();
            q2.pop_front();
        }
        balance();
        return res;
    }
    int popMiddle() {
        if (empty()) return -1;
        int res;
        if (q1.size() == q2.size()) {
            res = q1.back();
            q1.pop_back();
        } else {
            res = q2.front();
            q2.pop_front();
        }
        balance();
        return res;
    }
    int popBack() {
        if (empty()) return -1;
        int res = q2.back();
        q2.pop_back();
        balance();
        return res;
    }
    int empty() { return q1.size() + q2.size() == 0; }
};