publicvoidpush(int x) { stack.push(x); if (x > max) { max = x; } }

publicintpop() { // assume not empty intval= stack.pop(); if (val == max) { // update max (find the new max) intnewMax= Integer.MIN_VALUE; // consider size = 1, min should be reset // put aside while (stack.size() > 0) { intx= stack.pop(); newMax = Math.max(newMax, x); buffer.push(x); } max = newMax; // put it back while (buffer.size() > 0) { stack.push(buffer.pop()); } } return val; }

publicinttop() { return stack.peek(); }

publicintpeekMax() { return max; }

publicintpopMax() { intnewMax= Integer.MIN_VALUE; // find the max while (stack.peek() != max) { newMax = Math.max(newMax, stack.peek()); buffer.push(stack.pop()); } // remove max stack.pop(); // still put all to the buffer (we want to find newMax) while (stack.size() > 0) { newMax = Math.max(newMax, stack.peek()); buffer.push(stack.pop()); } // put back while (buffer.size() > 0) { stack.push(buffer.pop()); } intoldMax= max; max = newMax; return oldMax; } }

publicintpopMax() { intmax= maxStack.peek(); while (stack.peek() != max) { buffer.push(pop()); // pop from two stacks } pop(); // remove max while (buffer.size() > 0) { push(buffer.pop()); // push into two stacks } return max; } }

Note:

The following popMax() is not correct. Why? Use stack.pop() or pop()? Or use which push()?

1 2 3 4 5 6 7 8 9 10 11

// bug! publicintpopMax() { while (stack.peek() != maxStack.peek()) { buffer.push(stack.pop()); } stack.pop(); // remove max while (buffer.size() > 0) { stack.push(buffer.pop()); } return maxStack.pop(); }

Time: Only popMax() takes $O(N)$ Space: $O(N)$

The optimization can be made in finding the largest element by TreeMap.