Welcome to Subscribe On Youtube

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 { 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(); */ 
  • 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: # non-empty guaranteed, or else first if for both empty will return  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 # q1-size <= q2-size <= 1 + q1-size  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()  
  • 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() */

All Problems

All Solutions