help implementing All Nearest Smaller Values algorithm

Posted by davit-datuashvili on Stack Overflow See other posts from Stack Overflow or by davit-datuashvili
Published on 2010-05-14T21:28:09Z Indexed on 2010/05/14 21:54 UTC
Read the original article Hit count: 180

Filed under:
|
|

http://en.wikipedia.org/wiki/All_nearest_smaller_values this is 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 pseudo code from 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

© Stack Overflow or respective owner

Related posts about algorithms

Related posts about homework