Finding Maximum Element In Stack in Constant Time
Stack is an abstract data type supporting the operations Push() and Pop(). In this problem, you goal will be to design a stack that also supports finding the maximum element in stack in constant time.
Input Format
The first line of the input contains the number q of queries. Each of the following q lines specifies a query of one of the following formats: push v, pop, or max.
Output Format
For each max query, output (on a separate line) the maximum value of the stack.
Sample 1
Input:
4
push 10
max
push 5
max
push 15
max
Output:
10
10
15
Sample 1
Input:
5
push 1
push 2
max
pop
max
Output:
2
1
Approach :
- We are using another auxilary stack (maxStack) to store the max elements.
- For example, if new element pushed is greater than top element in maxStack , it will be pushed to maxStack
- For each max query we return the top element in maxStack.
- Top element from the maxStack is popped if element popped from the original stack is equal to the top element in maxStack.
Program
import java.util.*;
import java.io.*;
public class StackWithMax {
public void solve() throws IOException {
Scanner scanner = new Scanner(System.in);
int queries = scanner.nextInt();
Stack stack = new Stack();
Stack maxStack = new Stack();
for (int qi = 0; qi < queries; ++qi) {
String operation = scanner.next();
if ("push".equals(operation))
{
int value = scanner.nextInt();
stack.push(value);
if(maxStack.empty() || (value >= maxStack.peek()))
{
maxStack.push(value);
}
} else if ("pop".equals(operation)) {
if(!stack.empty())
{
int top = stack.peek();
int max = maxStack.peek();
if(top == max)
{
maxStack.pop();
}
stack.pop();
}
} else if ("max".equals(operation)) {
System.out.println(maxStack.peek());
}
}
}
static public void main(String[] args) throws IOException {
new StackWithMax().solve();
}
}
Finding maximum element in stack Analysis
Pop() – O(1) complexity
Push() – O(1) time complexity
Max() – O(1) time complexity
