Skip to content

1670. Design Front Middle Back Queue 👍

  • Time:
    • Constructor: $O(1)$
    • pushFront(val: int): $O(1)$
    • pushMiddle(val: int): $O(1)$
    • pushBack(val: int): $O(1)$
    • popFront(): $O(1)$
    • popMiddle(): $O(1)$
    • popBack(): $O(1)$
  • Space: $O(|\texttt{pushFront()}| + |\texttt{pushMiddle()}| + |\texttt{pushBack()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
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);
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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())