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)Addsvalto the front of the queue.void pushMiddle(int val)Addsvalto the middle of the queue.void pushBack(int val)Addsvalto 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
6into 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]returns3and 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
1000calls will be made topushFront,pushMiddle,pushBack,popFront,popMiddle, andpopBack.
class FrontMiddleBackQueue:
def __init__(self):
self.left = deque()
self.right = deque()
def pushFront(self, val: int) -> None:
self.left.appendleft(val)
self.rebalance()
def pushMiddle(self, val: int) -> None:
self.left.append(val)
self.rebalance()
def pushBack(self, val: int) -> None:
self.right.append(val)
self.rebalance()
def popFront(self) -> int:
if self.empty():
return -1
if self.left:
val = self.left.popleft()
else:
val = self.right.popleft()
self.rebalance()
return val
def popMiddle(self) -> int:
if self.empty():
return -1
if len(self.left) >= len(self.right):
val = self.left.pop()
else:
val = self.right.popleft()
self.rebalance()
return val
def popBack(self) -> int:
if self.empty():
return -1
val = self.right.pop()
self.rebalance()
return val
def empty(self) -> bool:
return not self.left and not self.right
def rebalance(self) -> None:
while len(self.left) > len(self.right):
self.right.appendleft(self.left.pop())
while len(self.right) - len(self.left) > 1:
self.left.append(self.right.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> left;
private Deque<Integer> right;
public FrontMiddleBackQueue() {
left = new LinkedList<>();
right = new LinkedList<>();
}
public void pushFront(int val) {
left.offerFirst(val);
rebalance();
}
public void pushMiddle(int val) {
left.offerLast(val);
rebalance();
}
public void pushBack(int val) {
right.offerLast(val);
rebalance();
}
public int popFront() {
if (empty()) {
return -1;
}
int val = left.isEmpty() ? right.pollFirst() : left.pollFirst();
rebalance();
return val;
}
public int popMiddle() {
if (empty()) {
return -1;
}
int val = left.size() >= right.size() ? left.pollLast() : right.pollFirst();
rebalance();
return val;
}
public int popBack() {
if (empty()) {
return -1;
}
int val = right.pollLast();
rebalance();
return val;
}
private boolean empty() {
return left.isEmpty() && right.isEmpty();
}
private void rebalance() {
while (left.size() > right.size()) {
right.offerFirst(left.pollLast());
}
while (right.size() - left.size() > 1) {
left.offerLast(right.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();
*/var FrontMiddleBackQueue = function () {
this.left = [];
this.right = [];
};
/**
* @param {number} val
* @return {void}
*/
FrontMiddleBackQueue.prototype.pushFront = function (val) {
this.left.unshift(val);
this.rebalance();
};
/**
* @param {number} val
* @return {void}
*/
FrontMiddleBackQueue.prototype.pushMiddle = function (val) {
this.left.push(val);
this.rebalance();
};
/**
* @param {number} val
* @return {void}
*/
FrontMiddleBackQueue.prototype.pushBack = function (val) {
this.right.push(val);
this.rebalance();
};
/**
* @return {number}
*/
FrontMiddleBackQueue.prototype.popFront = function () {
if (this.isEmpty()) return -1;
let num = this.left.length == 0 ? this.right.shift() : this.left.shift();
this.rebalance();
return num;
};
/**
* @return {number}
*/
FrontMiddleBackQueue.prototype.popMiddle = function () {
if (this.isEmpty()) return -1;
let num =
this.left.length == this.right.length
? this.left.pop()
: this.right.shift();
this.rebalance();
return num;
};
/**
* @return {number}
*/
FrontMiddleBackQueue.prototype.popBack = function () {
if (this.isEmpty()) return -1;
let num = this.right.pop();
this.rebalance();
return num;
};
FrontMiddleBackQueue.prototype.rebalance = function () {
while (this.left.length > this.right.length) {
this.right.unshift(this.left.pop());
}
while (this.right.length > this.left.length + 1) {
this.left.push(this.right.shift());
}
};
FrontMiddleBackQueue.prototype.isEmpty = function () {
return this.left.length == 0 && this.right.length == 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()
*/