Computer scienceProgramming languagesJavaWorking with dataCollectionsCollection implementationsThe Collection hierarchy implementations

Stack

Theory

Getting the max element of a stack

Report a typo

Write a program simulating a stack that can effectively return the current max element. Your program should read a sequence of commands of different types from the standard input.

There are three types of commands:

  • push v is to add an element (v) to the top of the stack;

  • pop is to remove the top element of the stack;

  • max is to return the current max in the stack.

The time complexity of these operations should not depend on the stack size (constant time, O(1)).

Hint: you may use several standard stacks to write a solution.

Input data format

The first line contains the number of commands. The next lines contain one of the following commands: push v, pop, max.

Output data format

The program must output the current max for each command max.

Note, that if your methods have time complexity more than O(1), your solution will not be accepted by timeout restriction.

Sample Input 1: 

5
push 2
push 1
max
pop
max

Sample Output 1: 

2
2

Sample Input 2: 

5
push 1
push 2
max
pop
max

Sample Output 2: 

2
1

Sample Input 3: 

10
push 2
push 3
push 9
push 7
push 2
max
max
max
pop
max

Sample Output 3: 

9
9
9
9
Write a program in Java 25
import java.util.Objects;
import java.util.Scanner;
import java.util.Stack;

class Main {
public static void main(String[] args) {
// put your code here
Scanner scanner = new Scanner(System.in);
Stack<Integer> stack = new Stack<>();
Stack<Integer> maxStack = new Stack<>();
maxStack.push(Integer.MIN_VALUE);
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
String input = scanner.next();
if ("push".equals(input)) {
int value = scanner.nextInt();
stack.push(value);
if (maxStack.peek() <= value) {
maxStack.push(value);
}
} else if ("pop".equals(input)) {
if (!stack.isEmpty() && Objects.equals(maxStack.peek(), stack.peek())) {
maxStack.pop();
}
if (!stack.isEmpty()) {
stack.pop();
}
} else if ("max".equals(input)) {
if (!maxStack.isEmpty()) {
System.out.println(maxStack.peek());
}
} else {
System.out.println("Unknown command: " + input);
}
}
}

Create a free account to access the full topic