I have written the below program to write a Java stack implementation. I have added a method which returns the maximum value in the stack, e.g, a pop. The implementation for this is based on the Max Heap Sort algorithim. I have little doubt on the time complexity analysis - it's not \$O(\log n)\$ is it?
public class Stack {
int top = -1;
int[] stack;
public Stack(int size) {
stack = new int[size];
}
public void push(int v) {
if (top == stack.length - 1) {
System.out.println("Oveflow!!");
return;
}
stack[++top] = v;
}
public void pop() {
if (top < 0) {
System.out.println("Empty stack");
return;
}
stack[top] = 0;
top--;
}
public int getMax() {
int[] c = stack.clone();
// not a complete heap sort, but with below approach, i am trying bubble up.
// build the heap starting from n/2, as any nodes after n/2 are leaf(s)
for (int j = stack.length / 2; j >= 0; j--) {
buildMaxHeap(c, j, c.length - 1);
}
return c[0];
}
private void buildMaxHeap(int[] clone, int i, int j) {
int root = i;
while (root * 2 + 1 <= j) {
int c = root * 2 + 1;
if ((c + 1) <= j && clone[c] <= clone[c + 1]) {
c = c + 1;
}
if (clone[root] < clone[c]) {
int t = clone[root];
clone[root] = clone[c];
clone[c] = t;
root = c;
} else {
root++;
}
}
}
public void display() {
System.out.println("------------------------");
for (int i = top; i >= 0; i--) {
System.out.println(stack[i]);
}
}
}