from collections import deque
class FrontMiddleBackQueue:
def __init__(self):
self.front = deque()
self.back = deque()
def balance(self):
# Maintain: len(front) == len(back) or len(front) == len(back) + 1
while len(self.front) > len(self.back) + 1:
self.back.appendleft(self.front.pop())
while len(self.front) < len(self.back):
self.front.append(self.back.popleft())
def pushFront(self, val: int) -> None:
self.front.appendleft(val)
self.balance()
def pushMiddle(self, val: int) -> None:
if len(self.front) > len(self.back):
self.back.appendleft(self.front.pop())
self.front.append(val)
self.balance()
def pushBack(self, val: int) -> None:
self.back.append(val)
self.balance()
def popFront(self) -> int:
if not self.front and not self.back:
return -1
if self.front:
val = self.front.popleft()
else:
val = self.back.popleft()
self.balance()
return val
def popMiddle(self) -> int:
if not self.front and not self.back:
return -1
val = self.front.pop()
self.balance()
return val
def popBack(self) -> int:
if not self.front and not self.back:
return -1
if self.back:
val = self.back.pop()
else:
val = self.front.pop()
self.balance()
return val
#include <deque>
using namespace std;
class FrontMiddleBackQueue {
public:
deque<int> front, back;
void balance() {
while (front.size() > back.size() + 1)
back.push_front(front.back()), front.pop_back();
while (front.size() < back.size())
front.push_back(back.front()), back.pop_front();
}
FrontMiddleBackQueue() {}
void pushFront(int val) {
front.push_front(val);
balance();
}
void pushMiddle(int val) {
if (front.size() > back.size())
back.push_front(front.back()), front.pop_back();
front.push_back(val);
balance();
}
void pushBack(int val) {
back.push_back(val);
balance();
}
int popFront() {
if (front.empty() && back.empty()) return -1;
int val;
if (!front.empty()) {
val = front.front(); front.pop_front();
} else {
val = back.front(); back.pop_front();
}
balance();
return val;
}
int popMiddle() {
if (front.empty() && back.empty()) return -1;
int val = front.back(); front.pop_back();
balance();
return val;
}
int popBack() {
if (front.empty() && back.empty()) return -1;
int val;
if (!back.empty()) {
val = back.back(); back.pop_back();
} else {
val = front.back(); front.pop_back();
}
balance();
return val;
}
};
import java.util.*;
class FrontMiddleBackQueue {
Deque<Integer> front, back;
public FrontMiddleBackQueue() {
front = new ArrayDeque<>();
back = new ArrayDeque<>();
}
private void balance() {
while (front.size() > back.size() + 1)
back.addFirst(front.removeLast());
while (front.size() < back.size())
front.addLast(back.removeFirst());
}
public void pushFront(int val) {
front.addFirst(val);
balance();
}
public void pushMiddle(int val) {
if (front.size() > back.size())
back.addFirst(front.removeLast());
front.addLast(val);
balance();
}
public void pushBack(int val) {
back.addLast(val);
balance();
}
public int popFront() {
if (front.isEmpty() && back.isEmpty()) return -1;
int val;
if (!front.isEmpty()) {
val = front.removeFirst();
} else {
val = back.removeFirst();
}
balance();
return val;
}
public int popMiddle() {
if (front.isEmpty() && back.isEmpty()) return -1;
int val = front.removeLast();
balance();
return val;
}
public int popBack() {
if (front.isEmpty() && back.isEmpty()) return -1;
int val;
if (!back.isEmpty()) {
val = back.removeLast();
} else {
val = front.removeLast();
}
balance();
return val;
}
}
class FrontMiddleBackQueue {
constructor() {
this.front = [];
this.back = [];
}
balance() {
while (this.front.length > this.back.length + 1) {
this.back.unshift(this.front.pop());
}
while (this.front.length < this.back.length) {
this.front.push(this.back.shift());
}
}
pushFront(val) {
this.front.unshift(val);
this.balance();
}
pushMiddle(val) {
if (this.front.length > this.back.length) {
this.back.unshift(this.front.pop());
}
this.front.push(val);
this.balance();
}
pushBack(val) {
this.back.push(val);
this.balance();
}
popFront() {
if (this.front.length === 0 && this.back.length === 0) return -1;
let val;
if (this.front.length) {
val = this.front.shift();
} else {
val = this.back.shift();
}
this.balance();
return val;
}
popMiddle() {
if (this.front.length === 0 && this.back.length === 0) return -1;
let val = this.front.pop();
this.balance();
return val;
}
popBack() {
if (this.front.length === 0 && this.back.length === 0) return -1;
let val;
if (this.back.length) {
val = this.back.pop();
} else {
val = this.front.pop();
}
this.balance();
return val;
}
}
You are asked to design a queue-like data structure that supports efficient operations at the front, middle, and back. Specifically, you must implement a class FrontMiddleBackQueue with the following operations:
pushFront(val): Insert val at the front of the queue.pushMiddle(val): Insert val in the middle of the queue. If the queue has an even length, insert just before the middle (i.e., at len/2).pushBack(val): Insert val at the back of the queue.popFront(): Remove and return the value at the front. If the queue is empty, return -1.popMiddle(): Remove and return the value in the middle. If the queue has an even length, remove the left-middle element. If empty, return -1.popBack(): Remove and return the value at the back. If the queue is empty, return -1.All operations must be efficient, ideally in constant or logarithmic time. You should not reuse elements or leave "holes" in the data structure. Each operation must maintain the correct order and structure of the queue.
At first glance, the problem seems similar to a standard queue or deque (double-ended queue), but the requirement to efficiently access and modify the middle element makes it more challenging.
collections.deque) is efficient at the ends but not in the middle.
To efficiently support all required operations, we use two double-ended queues (deques), named front and back:
front deque holds the first half (or one more if odd) of the elements, and back holds the rest.
front. For even-length queues, the left-middle is at the end of front.
pushFront: Insert at the front of front.pushBack: Insert at the back of back.pushMiddle: Ensure both halves are balanced, then insert at the end of front.popFront: Remove from the front of front (or from back if front is empty).popBack: Remove from the back of back (or from front if back is empty).popMiddle: Remove from the end of front.front allowed to have one more element if the total size is odd.
This approach ensures all operations are O(1) amortized, since deques allow fast insertions and deletions at both ends.
Let's walk through a sequence of operations:
pushFront(1) → Queue: [1]pushBack(2) → Queue: [1, 2]pushMiddle(3) → Queue: [1, 3, 2]popMiddle() → Returns 3, Queue: [1, 2]popFront() → Returns 1, Queue: [2]popBack() → Returns 2, Queue: []popFront() → Returns -1 (queue is empty)
At each step, after insertion or removal, the data structure balances the front and back deques so that the middle element is always efficiently accessible.
front or back.
By splitting the queue into two balanced deques, we enable constant-time access to the front, back, and middle elements. The clever use of balancing after each operation keeps the data structure efficient and simple. This approach elegantly solves the challenge of supporting O(1) operations for all required methods, making it a powerful and practical solution for this problem.