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.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()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();
*/type FrontMiddleBackQueue struct{}
var a []int
func Constructor() (_ FrontMiddleBackQueue) {
a = nil
return
}
func (FrontMiddleBackQueue) PushFront(v int) {
a = append([]int{v}, a...)
}
func (FrontMiddleBackQueue) PushMiddle(v int) {
p := len(a) / 2
a = append(a[:p], append([]int{v}, a[p:]...)...)
}
func (FrontMiddleBackQueue) PushBack(v int) {
a = append(a, v)
}
func (FrontMiddleBackQueue) PopFront() (ans int) {
if len(a) == 0 {
return -1
}
ans = a[0]
a = a[1:]
return
}
func (FrontMiddleBackQueue) PopMiddle() (ans int) {
if len(a) == 0 {
return -1
}
p := (len(a) - 1) / 2
ans = a[p]
a = append(a[:p], a[p+1:]...)
return
}
func (FrontMiddleBackQueue) PopBack() (ans int) {
if len(a) == 0 {
return -1
}
ans = a[len(a)-1]
a = a[:len(a)-1]
return
}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()
*/