Help implementing the All Nearest Smaller Values algorithm

Question

http://en.wikipedia.org/wiki/All_nearest_smaller_values. This is the site of the problem and here is my code, but I have some trouble to implement it:

import java.util.*;
public class stack{

    public static void main(String[]args){

        int x[]=new int[]{  0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };

        Stack<Integer> st=new Stack<Integer>();

        for (int a:x){
            while (!st.empty() && st.pop()>=a){
                System.out.println( st.pop());
                if (st.empty()){
                    break;
                }
                else{
                    st.push(a);
                }
            }
        }
    }
}

And here is the pseudo code from the site:

S = new empty stack data structure
for x in the input sequence:
    while S is nonempty and the top element of S is greater than or equal to x:
        pop S
    if S is empty:
        x has no preceding smaller value
    else:
        the nearest smaller value to x is the top element of S
    push x onto S

What is the matter with my code?

Answer 1

The method pop() doesn't do what you think it does. You should read the Stack documentation.

Answer 2

Here is the same pseudo code but I've added brackets so you can see where each statement begins and ends.

S = new empty stack data structure
for x in the input sequence:
{
    // peek instead of pop when you're checking what's in the queue
    while S is nonempty and the top element of S is greater than or equal to x:
    {
        pop S // you can call pop here
    }

    if S is empty:  // just check if the queue is empty, don't peek or pop
    {
        x has no preceding smaller value
    }
    else:
    {
        the nearest smaller value to x is the top element of S
    }
    push x onto S
}

You had the if/else statement inside the while loop, which was incorrect.

Check the documentation of the stack to understand what push, pop and peek do, here is the documentation: http://java.sun.com/j2se/1.4.2/docs/api/java/util/Stack.html

Answer 3

In the posted pseudocode the while is separate from the if/else; in your Java code the if is inside the while.

Also pop() removes the top element of the stack. You cannot use it to peek at the first element in the condition of while.

Answer 4

Will something like this work?

int[] inputSequence = new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5,
                                 13, 3, 11, 7, 15 };
Stack<Integer> S = new Stack<Integer>(); // empty stack data structure
for (int x : inputSequence) {
    while (!S.isEmpty() && topElementOf(S) >= x) {
        S.pop();
    }

    if (S.isEmpty())
        System.out.println(x + " has no preceding smaller value");
    else {
        System.out.println("the nearest smaller value to " + x + " is "
                    + topElementOf(S));
    }
    S.push(x);
}


private Integer topElementOf(Stack<Integer> stack) {
    return stack.peek();
}