Deque with 3 stacks

Java: Implement a deque by using three stacks. The queue should provide size(), isEmpty(), offerFirst(), offerLast(), pollFirst(), pollLast(), peekFirst() and peekLast() operations. When the queue is empty, pollFirst(), pollLast(), peekFirst() and peek() should return null.

Python: Implement a deque by using three stacks. The queue should provide size(), isEmpty(), offerFirst(), offerLast(), pollFirst(), pollLast(), peekFirst() and peekLast() operations. When the queue is empty, pollFirst(), pollLast(), peekFirst() and peek() should return None

C++: Implement a deque by using three stacks. The queue should provide size(), isEmpty(), push_front(), push_back(), pop_front(), pop_back(), front() and back() operations. When the queue is empty, front() and back() should return -1.

Assumptions

The elements in the queue are all Integers.

size() should return the number of elements buffered in the queue.

isEmpty() should return true if there is no element buffered in the queue, false otherwise.

The amortized time complexity of all operations should be O(1).

Solution: back to back stacks and one tmp stack

Use two opposite-facing stacks to acts as a queue.

Key Function: balance

When one of the stacks is empty but needs to complete a poll. The first element from the bottom must be gotten. To

public class Solution {

  private Deque<Integer> forward;
  private Deque<Integer> backward;
  private Deque<Integer> tmp;

  public Solution() {
    this.forward = new ArrayDeque<>();
    this.backward = new ArrayDeque<>();
    this.tmp = new ArrayDeque<>();
  }
  
  public void offerFirst(int element) {
    forward.offerFirst(element);
  }
  
  public void offerLast(int element) {
    backward.offerFirst(element);
  }
  
  public Integer pollFirst() {
    if(forward.isEmpty()){
      if(balance(backward, forward)){ //balance fails if only one element in backwards stack
        return forward.pollFirst();
      } else { 
        return backward.pollFirst();
      }
    } else {
      return forward.pollFirst();
    }
  }
  
  public Integer pollLast() {
    if (backward.isEmpty()){
      if(balance(forward, backward)){
        return backward.pollFirst();
      } else {
        return forward.pollFirst();
      }
    } else {
      return backward.pollFirst();
    }
  }
  
  public Integer peekFirst() {
    if(forward.isEmpty()){
      return peekBottom(backward);
    } else {
      return forward.peekFirst();
    }
  }
  
  public Integer peekLast() {
    if(backward.isEmpty()){
      return peekBottom(forward);
    } else {
      return backward.peekFirst();
    }
  }
  
  public int size() {
    return forward.size() + backward.size();
  }
  
  public boolean isEmpty() {
    return forward.isEmpty() && backward.isEmpty();
  }

  private boolean balance(Deque<Integer> full, Deque<Integer> empty){
    int size = full.size();
    if (size == 1) return false; //unable to balance 1 size stack

    for (int i = 0; i < size / 2; i++){
      tmp.offerFirst(full.pollFirst()); // move half of full to tmp
    }

    while(!full.isEmpty()){
      empty.offerFirst(full.pollFirst()); // move remaining to empty stack
    }

    while(!tmp.isEmpty()){
      full.offerFirst(tmp.pollFirst());
    }
    return true;
  }

  private Integer peekBottom(Deque<Integer> stack){
    while(!stack.isEmpty()){
      tmp.offerFirst(stack.pollFirst());
    }
    Integer result = tmp.peekFirst();
    while(!tmp.isEmpty()){
      stack.offerFirst(tmp.pollFirst());
    }
    return result;
  }
}