Formatted question description: https://leetcode.ca/all/1670.html
1670. Design Front Middle Back Queue
Level
Medium
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)
Addsval
to the front of the queue.void pushMiddle(int val)
Addsval
to the middle of the queue.void pushBack(int val)
Addsval
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]
returns3
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 <= 10^9
- At most
1000
calls will be made topushFront
,pushMiddle
,pushBack
,popFront
,popMiddle
, andpopBack
.
Solution
Easy way, to use 2 queues.
class FrontMiddleBackQueue {
Deque<Integer> left;
Deque<Integer> right;
public FrontMiddleBackQueue() {
left = new LinkedList<>();
right = new LinkedList<>();
}
public void pushFront(int val) {
left.offerFirst(val);
// right is 1-more than left, or equal
if (left.size() > right.size()) right.offerFirst(left.pollLast());
}
public void pushMiddle(int val) {
if (left.size() == right.size()) right.offerFirst(val);
else left.offerLast(val);
}
public void pushBack(int val) {
if (left.size() < right.size()) left.offerLast(right.pollFirst());
right.offerLast(val);
}
public int popFront() {
if (left.size() < right.size()) left.offerLast(right.pollFirst());
return left.isEmpty() ? -1 : left.pollFirst();
}
public int popMiddle() {
if (left.size() == right.size()) return left.isEmpty() ? -1 : left.pollLast();
else return right.isEmpty() ? -1 : right.pollFirst();
}
public int popBack() {
if (left.size() == right.size() && !left.isEmpty()) right.offerFirst(left.pollLast());
return right.isEmpty() ? -1 : right.pollLast();
}
}
Define a class Node
that links to both its previous node and its next node.
In FrontMiddleBackQueue
class, maintain the size, the start node, the end node and the middle node. Initially, the size is 0, and the start node, the end node and the middle node are all null
.
When pushing a value, update the nodes accordingly and increase the size by 1.
When popping a value, update the nodes accordingly and decrease the size by 1.
Java
import java.util.ArrayDeque;
import java.util.Deque;
class FrontMiddleBackQueue {
private Deque<Integer> fDeq, rDeq;
private int size;
public FrontMiddleBackQueue() {
fDeq = new ArrayDeque<>();
rDeq = new ArrayDeque<>();
}
public void pushFront(int val) {
fDeq.offerFirst(val);
adjust();
size++;
}
public void pushMiddle(int val) {
fDeq.offerLast(val);
adjust();
size++;
}
public void pushBack(int val) {
rDeq.offerLast(val);
adjust();
size++;
}
public int popFront() {
if (size == 0) {
return -1;
}
// 注意要判断一下前队列是否空
int res = !fDeq.isEmpty() ? fDeq.pollFirst() : rDeq.pollFirst();
adjust();
size--;
return res;
}
public int popMiddle() {
if (size == 0) {
return -1;
}
// 如果两个队列size一样,则pop前队列队尾,否则pop后队列队头
int res = fDeq.size() == rDeq.size() ? fDeq.pollLast() : rDeq.pollFirst();
adjust();
size--;
return res;
}
public int popBack() {
if (size == 0) {
return -1;
}
int res = rDeq.pollLast();
adjust();
size--;
return res;
}
// 用于调整两个队列的size,保持后半始终不少于前半,并且多不超过1个
private void adjust() {
if (rDeq.size() - fDeq.size() >= 2) {
fDeq.offerLast(rDeq.pollFirst());
}
if (rDeq.size() < fDeq.size()) {
rDeq.offerFirst(fDeq.pollLast());
}
}
}
class FrontMiddleBackQueue {
int size;
Node start;
Node end;
Node middle;
public FrontMiddleBackQueue() {
size = 0;
start = null;
end = null;
middle = null;
}
public void pushFront(int val) {
Node node = new Node(val);
if (size == 0) {
start = node;
end = node;
middle = node;
} else {
node.next = start;
start.prev = node;
start = node;
if (size % 2 == 1)
middle = middle.prev;
}
size++;
}
public void pushMiddle(int val) {
Node node = new Node(val);
if (size == 0) {
start = node;
end = node;
middle = node;
size++;
} else if (size == 1)
pushFront(val);
else {
if (size % 2 == 0) {
Node next = middle.next;
middle.next = node;
node.prev = middle;
next.prev = node;
node.next = next;
} else {
Node prev = middle.prev;
middle.prev = node;
node.next = middle;
prev.next = node;
node.prev = prev;
}
middle = node;
size++;
}
}
public void pushBack(int val) {
Node node = new Node(val);
if (size == 0) {
start = node;
end = node;
middle = node;
} else {
node.prev = end;
end.next = node;
end = node;
if (size % 2 == 0)
middle = middle.next;
}
size++;
}
public int popFront() {
if (size == 0)
return -1;
int val = start.val;
if (size == 1) {
start = null;
end = null;
middle = null;
size--;
return val;
} else {
start.next.prev = null;
start = start.next;
if (size % 2 == 0)
middle = middle.next;
size--;
return val;
}
}
public int popMiddle() {
if (size == 0)
return -1;
int val = middle.val;
if (size == 1) {
start = null;
end = null;
middle = null;
size--;
return val;
} else if (size == 2)
return popFront();
else {
Node prev = middle.prev, next = middle.next;
prev.next = next;
next.prev = prev;
if (size % 2 == 1)
middle = prev;
else
middle = next;
size--;
return val;
}
}
public int popBack() {
if (size == 0)
return -1;
int val = end.val;
if (size == 1) {
start = null;
end = null;
middle = null;
size--;
return val;
} else {
end.prev.next = null;
end = end.prev;
if (size % 2 == 1)
middle = middle.prev;
size--;
return val;
}
}
}
class Node {
int val;
Node prev;
Node next;
public Node(int val) {
this.val = val;
}
}
/**
* 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();
*/