# Linked in Onsite round 1 - Max Stack

unknown
java
2 years ago
3.1 kB
1
Indexable
Never
```/**
* 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);
}

/** 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;
}

}```