The requirements are to implement a mechanism in a Java Stack of integers to maintain and return the maximum value and be able to report it.
The first idea that comes up to mind is to use an Iterator. That works but is not as efficient (depending on how the stack is being used).
Following is a screen capture of the Eclipse IDE console:
6 <== number of entries
1 4 7 3 7 5 <== list of entries
main <<< N: 6
main <<< val: 1
main <<< val: 4
main <<< val: 7
main <<< val: 3
main <<< val: 7
main <<< val: 5
main <<< val: 5 maxVal: 7 iterMax: 7
main <<< val: 7 maxVal: 7 iterMax: 7
main <<< val: 3 maxVal: 7 iterMax: 7
main <<< val: 7 maxVal: 4 iterMax: 4
main <<< val: 4 maxVal: 1 iterMax: 1
main <<< val: 1
Following is test code written in Java:
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
// **** ****
MyStack stack = new MyStack();
Scanner sc = new Scanner(System.in);
int val;
int maxVal;
int iterMax;
// **** ****
int N = sc.nextInt();
System.out.println(“main <<< N: ” + N);
// **** push values into the stack ****
for (int n = 0; n < N; n++) {
val = sc.nextInt();
System.out.println(“main <<< val: ” + val);
stack.push(val);
}
System.out.println();
// **** pop values from the stack ****
while (!stack.isEmpty()) {
val = stack.pop();
if (!stack.isEmpty()) {
maxVal = stack.max();
iterMax = stack.maxValue();
System.out.println(“main <<< val: ” + val + ” maxVal: ” + maxVal + ” iterMax: ” + iterMax);
} else {
System.out.println(“main <<< val: ” + val);
}
}
// **** close scanner ****
sc.close();
}
}
The first loop is used to read the values for the test. As they are read they are pushed into the stack. These values are also display on the console.
The second loop is used to pop all the values from the stack. The iterMax value is obtained by using an Iterator over the stack. This operation in O(n). The maxVal value is obtained by using a stack. This operation is O(1). As one can tell, both values match.
The code for the derived class follows:
import java.util.Iterator;
import java.util.Stack;
public class MyStack extends Stack<Integer> {
// **** members ****
Stack<Integer> maxStack;
/**
* constructor
*/
MyStack() {
super();
maxStack = new Stack<Integer>();
}
/**
*
*/
public Integer pop() {
int val = (int)super.pop();
if (val == maxStack.peek()) {
maxStack.pop();
}
return val;
}
/**
*
*/
public void push(int val) {
super.push(val);
if (maxStack.isEmpty()) {
maxStack.push(val);
} else {
if (val >= maxStack.peek()) {
maxStack.push(val);
}
}
}
/**
* get current max value
*/
public int max() {
return maxStack.peek();
}
/**
*
*/
public int maxValue() {
int maxValue = Integer.MIN_VALUE;
Iterator iter = super.iterator();
while (iter.hasNext()) {
int val = (int)iter.next();
if (maxValue < val) {
maxValue = val;
}
}
return maxValue;
}
}
Of course one needs to think and experiment to come up with such algorithm. I was talking with an engineer and thinking about it. This like other algorithms tend to be simple after one knows the answer. That said; it was worth doing the challenge.
If you have comments or questions regarding this or any other post please send me a message. I will not use your name unless you explicitly allow me to do so.
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa