Leetcode 1670: Design Front Middle Back Queue

In this Leetcode problem, we are implementing a Queue from from with we can push and pop from the front, back, or middle.

Problem statement

Solution

Obviously, the pop and push from the middle are the core of the problem. Otherwise we could use a LinkedList.

To solve this problem, we break up the linked list into 2 linked lists. We split it in the middle, so that it is easier when we need to push or pop from the middle.

Now, the lists can become unbalanced, so we ensure that after each operations, the lists have the same sizes, or differ by 1 only, and if the sizes differ by one, then the back list is the bigger list.

So, we rebalance after each operation to ensure this is always the case.

Here is the implementation for rebalancing:

private void balance() {
  if (front.size() == back.size()) {
    return;
  }
  if (front.size() > back.size()) {
    frontToBack();
  }
  if (front.size() < back.size() - 1) {
    backToFront();
  }
}
    
private void frontToBack() {
  back.addFirst(front.removeLast());        
}
private void backToFront() {
  front.addLast(back.removeFirst());        
}

All the push operations are then implemented very simply: