Question

1670. Design Front Middle Back Queue

中文文档

Description

Design a queue that supports push and pop operations in the front, middle, and back.

Implement the FrontMiddleBack class:

• FrontMiddleBack() Initializes the queue.
• void pushFront(int val) Adds val to the front of the queue.
• void pushMiddle(int val) Adds val to the middle of the queue.
• void pushBack(int val) Adds val to the back of the queue.
• int popFront() Removes the front element of the queue and returns it. If the queue is empty, return -1.
• int popMiddle() Removes the middle element of the queue and returns it. If the queue is empty, return -1.
• int popBack() Removes the back element of the queue and returns it. If the queue is empty, return -1.

Notice that when there are two middle position choices, the operation is performed on the frontmost middle position choice. For example:

• Pushing 6 into the middle of [1, 2, 3, 4, 5] results in [1, 2, 6, 3, 4, 5].
• Popping the middle from [1, 2, 3, 4, 5, 6] returns 3 and results in [1, 2, 4, 5, 6].

 

Example 1:

Input:
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
Output:
[null, null, null, null, null, 1, 3, 4, 2, -1]

Explanation:
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();   // return 1 -> [4, 3, 2]
q.popMiddle();  // return 3 -> [4, 2]
q.popMiddle();  // return 4 -> [2]
q.popBack();    // return 2 -> []
q.popFront();   // return -1 -> [] (The queue is empty)

 

Constraints:

• 1 <= val <= 109
• At most 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.

Solutions

Solution 1: Two Deques

We use two deques, where $q_1$ stores the first half, and $q_2$ stores the second half. The rebalance function is used to maintain the balance between the two queues, i.e., keeping the length of $q_2$ greater than or equal to the length of $q_1$, and the difference in length does not exceed $1$.

In the pushFront, pushMiddle, and pushBack functions, we only need to add elements to $q_1$ or $q_2$, and call the rebalance function.

For the popFront function, we need to check whether $q_1$ and $q_2$ are empty. If both are empty, return $-1$. Otherwise, we need to check whether $q_1$ is empty. If not, pop the front element of $q_1$, otherwise pop the front element of $q_2$, and call the rebalance function.

For the popMiddle function, we need to check whether $q_1$ and $q_2$ are empty. If both are empty, return $-1$. Otherwise, we need to check whether the lengths of $q_1$ and $q_2$ are equal. If they are equal, pop the last element of $q_1$, otherwise pop the front element of $q_2$, and call the rebalance function.

For the popBack function, we only need to check whether $q_2$ is empty. If it is empty, return $-1$. Otherwise, pop the last element of $q_2$, and call the rebalance function.

The time complexity of the above operations is $O(1)$, and the space complexity is $O(n)$, where $n$ is the number of elements in the queue.

class FrontMiddleBackQueue:
  def __init__(self):
    self.q1 = deque()
    self.q2 = deque()

  def pushFront(self, val: int) -> None:
    self.q1.appendleft(val)
    self.rebalance()

  def pushMiddle(self, val: int) -> None:
    self.q1.append(val)
    self.rebalance()

  def pushBack(self, val: int) -> None:
    self.q2.append(val)
    self.rebalance()

  def popFront(self) -> int:
    if not self.q1 and not self.q2:
      return -1
    if self.q1:
      val = self.q1.popleft()
    else:
      val = self.q2.popleft()
    self.rebalance()
    return val

  def popMiddle(self) -> int:
    if not self.q1 and not self.q2:
      return -1
    if len(self.q1) == len(self.q2):
      val = self.q1.pop()
    else:
      val = self.q2.popleft()
    self.rebalance()
    return val

  def popBack(self) -> int:
    if not self.q2:
      return -1
    val = self.q2.pop()
    self.rebalance()
    return val

  def rebalance(self):
    if len(self.q1) > len(self.q2):
      self.q2.appendleft(self.q1.pop())
    if len(self.q2) > len(self.q1) + 1:
      self.q1.append(self.q2.popleft())


# Your FrontMiddleBackQueue object will be instantiated and called as such:
# obj = FrontMiddleBackQueue()
# obj.pushFront(val)
# obj.pushMiddle(val)
# obj.pushBack(val)
# param_4 = obj.popFront()
# param_5 = obj.popMiddle()
# param_6 = obj.popBack()

class FrontMiddleBackQueue {
  private Deque<Integer> q1 = new ArrayDeque<>();
  private Deque<Integer> q2 = new ArrayDeque<>();

  public FrontMiddleBackQueue() {
  }

  public void pushFront(int val) {
    q1.offerFirst(val);
    rebalance();
  }

  public void pushMiddle(int val) {
    q1.offerLast(val);
    rebalance();
  }

  public void pushBack(int val) {
    q2.offerLast(val);
    rebalance();
  }

  public int popFront() {
    if (q1.isEmpty() && q2.isEmpty()) {
      return -1;
    }
    int val = q1.isEmpty() ? q2.pollFirst() : q1.pollFirst();
    rebalance();
    return val;
  }

  public int popMiddle() {
    if (q1.isEmpty() && q2.isEmpty()) {
      return -1;
    }
    int val = q1.size() == q2.size() ? q1.pollLast() : q2.pollFirst();
    rebalance();
    return val;
  }

  public int popBack() {
    if (q2.isEmpty()) {
      return -1;
    }
    int val = q2.pollLast();
    rebalance();
    return val;
  }

  private void rebalance() {
    if (q1.size() > q2.size()) {
      q2.offerFirst(q1.pollLast());
    }
    if (q2.size() > q1.size() + 1) {
      q1.offerLast(q2.pollFirst());
    }
  }
}

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * FrontMiddleBackQueue obj = new FrontMiddleBackQueue();
 * obj.pushFront(val);
 * obj.pushMiddle(val);
 * obj.pushBack(val);
 * int param_4 = obj.popFront();
 * int param_5 = obj.popMiddle();
 * int param_6 = obj.popBack();
 */

class FrontMiddleBackQueue {
public:
  FrontMiddleBackQueue() {
  }

  void pushFront(int val) {
    q1.push_front(val);
    rebalance();
  }

  void pushMiddle(int val) {
    q1.push_back(val);
    rebalance();
  }

  void pushBack(int val) {
    q2.push_back(val);
    rebalance();
  }

  int popFront() {
    if (q1.empty() && q2.empty()) return -1;
    int val = 0;
    if (q1.size()) {
      val = q1.front();
      q1.pop_front();
    } else {
      val = q2.front();
      q2.pop_front();
    }
    rebalance();
    return val;
  }

  int popMiddle() {
    if (q1.empty() && q2.empty()) return -1;
    int val = 0;
    if (q1.size() == q2.size()) {
      val = q1.back();
      q1.pop_back();
    } else {
      val = q2.front();
      q2.pop_front();
    }
    rebalance();
    return val;
  }

  int popBack() {
    if (q2.empty()) return -1;
    int val = q2.back();
    q2.pop_back();
    rebalance();
    return val;
  }

private:
  deque<int> q1;
  deque<int> q2;

  void rebalance() {
    if (q1.size() > q2.size()) {
      q2.push_front(q1.back());
      q1.pop_back();
    }
    if (q2.size() > q1.size() + 1) {
      q1.push_back(q2.front());
      q2.pop_front();
    }
  }
};

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * FrontMiddleBackQueue* obj = new FrontMiddleBackQueue();
 * obj->pushFront(val);
 * obj->pushMiddle(val);
 * obj->pushBack(val);
 * int param_4 = obj->popFront();
 * int param_5 = obj->popMiddle();
 * int param_6 = obj->popBack();
 */

type FrontMiddleBackQueue struct {
  q1, q2 Deque
}

func Constructor() FrontMiddleBackQueue {
  return FrontMiddleBackQueue{}
}

func (this *FrontMiddleBackQueue) PushFront(val int) {
  this.q1.PushFront(val)
  this.rebalance()
}

func (this *FrontMiddleBackQueue) PushMiddle(val int) {
  this.q1.PushBack(val)
  this.rebalance()
}

func (this *FrontMiddleBackQueue) PushBack(val int) {
  this.q2.PushBack(val)
  this.rebalance()
}

func (this *FrontMiddleBackQueue) PopFront() int {
  if this.q1.Empty() && this.q2.Empty() {
    return -1
  }
  var val int
  if !this.q1.Empty() {
    val = this.q1.PopFront()
  } else {
    val = this.q2.PopFront()
  }
  this.rebalance()
  return val
}

func (this *FrontMiddleBackQueue) PopMiddle() int {
  if this.q1.Empty() && this.q2.Empty() {
    return -1
  }
  var val int
  if this.q1.Size() == this.q2.Size() {
    val = this.q1.PopBack()
  } else {
    val = this.q2.PopFront()
  }
  this.rebalance()
  return val
}

func (this *FrontMiddleBackQueue) PopBack() int {
  if this.q2.Empty() {
    return -1
  }
  val := this.q2.PopBack()
  this.rebalance()
  return val
}

func (this *FrontMiddleBackQueue) rebalance() {
  if this.q1.Size() > this.q2.Size() {
    this.q2.PushFront(this.q1.PopBack())
  }
  if this.q2.Size() > this.q1.Size()+1 {
    this.q1.PushBack(this.q2.PopFront())
  }
}

// template
type Deque struct{ l, r []int }

func (q Deque) Empty() bool {
  return len(q.l) == 0 && len(q.r) == 0
}

func (q Deque) Size() int {
  return len(q.l) + len(q.r)
}

func (q *Deque) PushFront(v int) {
  q.l = append(q.l, v)
}

func (q *Deque) PushBack(v int) {
  q.r = append(q.r, v)
}

func (q *Deque) PopFront() (v int) {
  if len(q.l) > 0 {
    q.l, v = q.l[:len(q.l)-1], q.l[len(q.l)-1]
  } else {
    v, q.r = q.r[0], q.r[1:]
  }
  return
}

func (q *Deque) PopBack() (v int) {
  if len(q.r) > 0 {
    q.r, v = q.r[:len(q.r)-1], q.r[len(q.r)-1]
  } else {
    v, q.l = q.l[0], q.l[1:]
  }
  return
}

func (q Deque) Front() int {
  if len(q.l) > 0 {
    return q.l[len(q.l)-1]
  }
  return q.r[0]
}

func (q Deque) Back() int {
  if len(q.r) > 0 {
    return q.r[len(q.r)-1]
  }
  return q.l[0]
}

func (q Deque) Get(i int) int {
  if i < len(q.l) {
    return q.l[len(q.l)-1-i]
  }
  return q.r[i-len(q.l)]
}

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.PushFront(val);
 * obj.PushMiddle(val);
 * obj.PushBack(val);
 * param_4 := obj.PopFront();
 * param_5 := obj.PopMiddle();
 * param_6 := obj.PopBack();
 */

class FrontMiddleBackQueue {
  private q1: Deque<number>;
  private q2: Deque<number>;

  constructor() {
    this.q1 = new Deque<number>();
    this.q2 = new Deque<number>();
  }

  pushFront(val: number): void {
    this.q1.pushFront(val);
    this.rebalance();
  }

  pushMiddle(val: number): void {
    this.q1.pushBack(val);
    this.rebalance();
  }

  pushBack(val: number): void {
    this.q2.pushBack(val);
    this.rebalance();
  }

  popFront(): number {
    if (this.q1.isEmpty() && this.q2.isEmpty()) {
      return -1;
    }
    const val = this.q1.isEmpty() ? this.q2.popFront() : this.q1.popFront();
    this.rebalance();
    return val!;
  }

  popMiddle(): number {
    if (this.q1.isEmpty() && this.q2.isEmpty()) {
      return -1;
    }
    const val =
      this.q1.getSize() === this.q2.getSize() ? this.q1.popBack() : this.q2.popFront();
    this.rebalance();
    return val!;
  }

  popBack(): number {
    if (this.q2.isEmpty()) {
      return -1;
    }
    const val = this.q2.popBack();
    this.rebalance();
    return val!;
  }

  private rebalance(): void {
    if (this.q1.getSize() > this.q2.getSize()) {
      this.q2.pushFront(this.q1.popBack()!);
    }
    if (this.q2.getSize() > this.q1.getSize() + 1) {
      this.q1.pushBack(this.q2.popFront()!);
    }
  }
}

class Node<T> {
  value: T;
  next: Node<T> | null;
  prev: Node<T> | null;

  constructor(value: T) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class Deque<T> {
  private front: Node<T> | null;
  private back: Node<T> | null;
  private size: number;

  constructor() {
    this.front = null;
    this.back = null;
    this.size = 0;
  }

  pushFront(val: T): void {
    const newNode = new Node(val);
    if (this.isEmpty()) {
      this.front = newNode;
      this.back = newNode;
    } else {
      newNode.next = this.front;
      this.front!.prev = newNode;
      this.front = newNode;
    }
    this.size++;
  }

  pushBack(val: T): void {
    const newNode = new Node(val);
    if (this.isEmpty()) {
      this.front = newNode;
      this.back = newNode;
    } else {
      newNode.prev = this.back;
      this.back!.next = newNode;
      this.back = newNode;
    }
    this.size++;
  }

  popFront(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.front!.value;
    this.front = this.front!.next;
    if (this.front !== null) {
      this.front.prev = null;
    } else {
      this.back = null;
    }
    this.size--;
    return value;
  }

  popBack(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.back!.value;
    this.back = this.back!.prev;
    if (this.back !== null) {
      this.back.next = null;
    } else {
      this.front = null;
    }
    this.size--;
    return value;
  }

  frontValue(): T | undefined {
    return this.front?.value;
  }

  backValue(): T | undefined {
    return this.back?.value;
  }

  getSize(): number {
    return this.size;
  }

  isEmpty(): boolean {
    return this.size === 0;
  }
}

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * var obj = new FrontMiddleBackQueue()
 * obj.pushFront(val)
 * obj.pushMiddle(val)
 * obj.pushBack(val)
 * var param_4 = obj.popFront()
 * var param_5 = obj.popMiddle()
 * var param_6 = obj.popBack()
 */

class FrontMiddleBackQueue {
  constructor() {
    this.q1 = new Deque();
    this.q2 = new Deque();
  }

  pushFront(val) {
    this.q1.pushFront(val);
    this.rebalance();
  }

  pushMiddle(val) {
    this.q1.pushBack(val);
    this.rebalance();
  }

  pushBack(val) {
    this.q2.pushBack(val);
    this.rebalance();
  }

  popFront() {
    if (this.q1.isEmpty() && this.q2.isEmpty()) {
      return -1;
    }
    const val = this.q1.isEmpty() ? this.q2.popFront() : this.q1.popFront();
    this.rebalance();
    return val !== undefined ? val : -1;
  }

  popMiddle() {
    if (this.q1.isEmpty() && this.q2.isEmpty()) {
      return -1;
    }
    const val =
      this.q1.getSize() === this.q2.getSize() ? this.q1.popBack() : this.q2.popFront();
    this.rebalance();
    return val !== undefined ? val : -1;
  }

  popBack() {
    if (this.q2.isEmpty()) {
      return -1;
    }
    const val = this.q2.popBack();
    this.rebalance();
    return val !== undefined ? val : -1;
  }

  rebalance() {
    if (this.q1.getSize() > this.q2.getSize()) {
      this.q2.pushFront(this.q1.popBack());
    }
    if (this.q2.getSize() > this.q1.getSize() + 1) {
      this.q1.pushBack(this.q2.popFront());
    }
  }
}

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class Deque {
  constructor() {
    this.front = null;
    this.back = null;
    this.size = 0;
  }

  pushFront(val) {
    const newNode = new Node(val);
    if (this.isEmpty()) {
      this.front = newNode;
      this.back = newNode;
    } else {
      newNode.next = this.front;
      this.front.prev = newNode;
      this.front = newNode;
    }
    this.size++;
  }

  pushBack(val) {
    const newNode = new Node(val);
    if (this.isEmpty()) {
      this.front = newNode;
      this.back = newNode;
    } else {
      newNode.prev = this.back;
      this.back.next = newNode;
      this.back = newNode;
    }
    this.size++;
  }

  popFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.front.value;
    this.front = this.front.next;
    if (this.front !== null) {
      this.front.prev = null;
    } else {
      this.back = null;
    }
    this.size--;
    return value;
  }

  popBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.back.value;
    this.back = this.back.prev;
    if (this.back !== null) {
      this.back.next = null;
    } else {
      this.front = null;
    }
    this.size--;
    return value;
  }

  frontValue() {
    return this.front?.value;
  }

  backValue() {
    return this.back?.value;
  }

  getSize() {
    return this.size;
  }

  isEmpty() {
    return this.size === 0;
  }
}

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * var obj = new FrontMiddleBackQueue()
 * obj.pushFront(val)
 * obj.pushMiddle(val)
 * obj.pushBack(val)
 * var param_4 = obj.popFront()
 * var param_5 = obj.popMiddle()
 * var param_6 = obj.popBack()
 */