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 q1 stores the first half, and q2 stores the second half. The rebalance function is used to maintain the balance between the two queues, i.e., keeping the length of q2 greater than or equal to the length of q1, and the difference in length does not exceed 1.
In the pushFront, pushMiddle, and pushBack functions, we only need to add elements to q1 or q2, and call the rebalance function.
For the popFront function, we need to check whether q1 and q2 are empty. If both are empty, return -1. Otherwise, we need to check whether q1 is empty. If not, pop the front element of q1, otherwise pop the front element of q2, and call the rebalance function.
For the popMiddle function, we need to check whether q1 and q2 are empty. If both are empty, return -1. Otherwise, we need to check whether the lengths of q1 and q2 are equal. If they are equal, pop the last element of q1, otherwise pop the front element of q2, and call the rebalance function.
For the popBack function, we only need to check whether q2 is empty. If it is empty, return -1. Otherwise, pop the last element of q2, 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.
PythonJavaC++GoTypeScriptJavaScript
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()(code-box)
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();
*/(code-box)
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();
*/(code-box)
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();
*/(code-box)
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()
*/(code-box)
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()
*/(code-box)
