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 pushFrontpushMiddlepushBack, 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()
*/