Linked in Onsite round 1 - Max Stack

/**
 * A stacklike data structure that also allows stacklike access
 * to its elements by their value.
 * For example, given a stack of {1, 3, 2, 5, 3, 4, 5, 2}
 * peek() -> 2, peekMax() -> 5
 * pop() -> 2; peek() -> 5, peekMax() -> 5
 * pop() -> 5; peek() -> 4, peekMax() -> 5
 * push(6); peek() -> 6, peekMax() -> 6
 * popMax() -> 6; peek -> 4, peekMax() -> 5
 * popMax() -> 5; peek -> 4, peekMax() -> 4
 
 maxStack -> 1, 3, 3, 5
 
 stack 1, 3, 2, 5
 maxStack 1,
 
 popmax() -> 5
 popmax() -> 3
 popmax() -> 2
 
 
 * Throw Exception when stack empty()
 
 Solution 1 - Max Heap + Stack (Linked List)
 push - O(Logn)
 peek - O(1)
 pop - O(Logn)
 peekMax - O(1)
 popMax - O(n)
 
 Solution 2 - Double Stack
 push - O(1)
 peek - O(1)
 pop - O(1)
 peekMax - O(1)
 popMax - O(n)
 
 * 
 */


// 5,4,3,2,1
  
// main stack 5,4,3,2,1
// max stack  5,5,5,5,5
  

  
// popMax
// 1,2,3,4


// 4,3,2,1
// 4,4,4,4
  
// 1,2,3,4
// 4
  
// Solution 3 - TreeMap , DoublyLinkedList
// TreeMap -> <Val, List<Position>>
// Doubly Linked List -> Integers
  

public interface MaxStack<T extends Comparable<T>> {
 
    // The standard three Stack methods:
    /** Add an element to the stack. */
    public void push(T toPush);
 
    /** Return the top value on the stack. */
    public T peek();
  
    /** Remove and return the top value from the stack. */
    public T pop();
     
    // Two special methods, so this isn't just 'implement a stack':
 
    /** Return the largest value in the stack. (Remember that T must implement Comparable.) */
    public T peekMax();
 
    /** Remove and return the largest value from the stack. */
    public T popMax();
}

public class MaxStackImpl implements MaxStack {
  
    Stack<Integer> maxStack;
    Stack<Integer> stack;
  
    public MaxStackImpl() {
      maxStack = new Stack<>();
      stack = new Stack<>();
    }
    // The standard three Stack methods:
    /** Add an element to the stack. */
    public void push(int toPush) {
      int max = maxStack.isEmpty() ? toPush : maxStack.peek();
      maxStack.push(max > toPush ? max : toPush);
      stack.add(toPush);
    }
 
    /** Return the top value on the stack. */
    public int peek() {
      return stack.peek();
    }
  
    /** Remove and return the top value from the stack. */
    public int pop() {
      stack.pop();
      return maxStack.pop();
    }
     
    // Two special methods, so this isn't just 'implement a stack':
 
    /** Return the largest value in the stack. (Remember that T must implement Comparable.) */
    public int peekMax() {
      return maxStack.peek();
    }
 
  
// main stack 1,3,2
// max stack 1,3,3
// newStack 2,3,1
// max = 5
  
// main stack 100,1,2,3
// max stack 100,100,100,100

    /** Remove and return the largest value from the stack. */
    public int popMax() {
      int max = peekMax();
      Stack<Integer> newStack = new Stack<>();
      while (stack.peek() != max) {
        int temp = pop();
        newStack.push(temp);
      }
      pop();
      while(!newStack.isEmpty()) {
        push(newStack.pop);
      }
      return max;
    }
  
}