1670. Design Front Middle Back Queue LeetCode Solution

In this guide, you will get 1670. Design Front Middle Back Queue LeetCode Solution with the best time and space complexity. The solution to Design Front Middle Back Queue problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Design Front Middle Back Queue solution in C++
4. Design Front Middle Back Queue solution in Java
5. Design Front Middle Back Queue solution in Python
6. Additional Resources

Problem Statement of Design Front Middle Back Queue

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.

Complexity Analysis

• Time Complexity: O(1)
• Space Complexity: O(|\texttt{pushFront()}| + |\texttt{pushMiddle()}| + |\texttt{pushBack()}|)

1670. Design Front Middle Back Queue LeetCode Solution in C++

class FrontMiddleBackQueue {
 public:
  void pushFront(int val) {
    frontQueue.push_front(val);
    moveFrontToBackIfNeeded();
  }

  void pushMiddle(int val) {
    if (| frontQueue | == | backQueue |)
      backQueue.push_front(val);
    else
      frontQueue.push_back(val);
  }

  void pushBack(int val) {
    backQueue.push_back(val);
    moveBackToFrontIfNeeded();
  }

  int popFront() {
    if (!frontQueue.empty()) {
      const int x = frontQueue.front();
      frontQueue.pop_front();
      moveBackToFrontIfNeeded();
      return x;
    }
    if (!backQueue.empty()) {
      const int x = backQueue.front();
      backQueue.pop_front();
      moveFrontToBackIfNeeded();
      return x;
    }
    return -1;
  }

  int popMiddle() {
    if (frontQueue.empty() && backQueue.empty())
      return -1;
    if (frontQueue.size() + 1 == backQueue.size()) {
      const int x = backQueue.front();
      backQueue.pop_front();
      return x;
    } else {  // |frontQueue| == |backQueue|
      const int x = frontQueue.back();
      frontQueue.pop_back();
      return x;
    }
  }

  int popBack() {
    if (backQueue.empty())
      return -1;
    const int x = backQueue.back();
    backQueue.pop_back();
    moveFrontToBackIfNeeded();
    return x;
  }

 private:
  // |frontQueue| = |backQueue| or
  // |frontQueue| = |backQueue| - 1
  deque<int> frontQueue;
  deque<int> backQueue;

  void moveFrontToBackIfNeeded() {
    if (frontQueue.size() - 1 == backQueue.size()) {
      const int x = frontQueue.back();
      frontQueue.pop_back();
      backQueue.push_front(x);
    }
  }

  void moveBackToFrontIfNeeded() {
    if (frontQueue.size() + 2 == backQueue.size()) {
      const int x = backQueue.front();
      backQueue.pop_front();
      frontQueue.push_back(x);
    }
  }
};
/* code provided by PROGIEZ */

1670. Design Front Middle Back Queue LeetCode Solution in Java

class FrontMiddleBackQueue {
  public void pushFront(int val) {
    frontQueue.offerFirst(val);
    moveFrontToBackIfNeeded();
  }

  public void pushMiddle(int val) {
    if (| frontQueue | == | backQueue |)
      backQueue.offerFirst(val);
    else
      frontQueue.offerLast(val);
  }

  public void pushBack(int val) {
    backQueue.offerLast(val);
    moveBackToFrontIfNeeded();
  }

  public int popFront() {
    if (!frontQueue.isEmpty()) {
      final int x = frontQueue.removeFirst();
      moveBackToFrontIfNeeded();
      return x;
    }
    if (!backQueue.isEmpty())
      return backQueue.pollFirst();
    return -1;
  }

  public int popMiddle() {
    if (frontQueue.isEmpty() && backQueue.isEmpty())
      return -1;
    if (frontQueue.size() + 1 == backQueue.size())
      return backQueue.pollFirst();
    // |frontQueue| == |backQueue|
    return frontQueue.pollLast();
  }

  public int popBack() {
    if (backQueue.isEmpty())
      return -1;
    final int x = backQueue.removeLast();
    moveFrontToBackIfNeeded();
    return x;
  }

  private void moveFrontToBackIfNeeded() {
    if (frontQueue.size() - 1 == backQueue.size())
      backQueue.offerFirst(frontQueue.pollLast());
  }

  private void moveBackToFrontIfNeeded() {
    if (frontQueue.size() + 2 == backQueue.size())
      frontQueue.offerLast(backQueue.pollFirst());
  }

  private Deque<Integer> frontQueue = new ArrayDeque<>();
  private Deque<Integer> backQueue = new ArrayDeque<>();
}
// code provided by PROGIEZ

1670. Design Front Middle Back Queue LeetCode Solution in Python

class FrontMiddleBackQueue:
  def __init__(self):
    self.frontQueue = collections.deque()
    self.backQueue = collections.deque()

  def pushFront(self, val: int) -> None:
    self.frontQueue.appendleft(val)
    self._moveFrontToBackIfNeeded()

  def pushMiddle(self, val: int) -> None:
    if len(self.frontQueue) == len(self.backQueue):
      self.backQueue.appendleft(val)
    else:
      self.frontQueue.append(val)

  def pushBack(self, val: int) -> None:
    self.backQueue.append(val)
    self._moveBackToFrontIfNeeded()

  def popFront(self) -> int:
    if self.frontQueue:
      x = self.frontQueue.popleft()
      self._moveBackToFrontIfNeeded()
      return x
    if self.backQueue:
      return self.backQueue.popleft()
    return -1

  def popMiddle(self) -> int:
    if not self.frontQueue and not self.backQueue:
      return -1
    if len(self.frontQueue) + 1 == len(self.backQueue):
      return self.backQueue.popleft()
    return self.frontQueue.pop()

  def popBack(self) -> int:
    if self.backQueue:
      x = self.backQueue.pop()
      self._moveFrontToBackIfNeeded()
      return x
    return -1

  def _moveFrontToBackIfNeeded(self) -> None:
    if len(self.frontQueue) - 1 == len(self.backQueue):
      self.backQueue.appendleft(self.frontQueue.pop())

  def _moveBackToFrontIfNeeded(self) -> None:
    if len(self.frontQueue) + 2 == len(self.backQueue):
      self.frontQueue.append(self.backQueue.popleft())
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.