Help implementing the All Nearest Smaller Values ​​algorithm

Question

http://en.wikipedia.org/wiki/All_nearest_smaller_values . This is the problem site and here is my code, but I have some problems with its implementation:

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 pseudocode 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 wrong with my code?

Answer 1

Here is the same pseudo code, but I 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 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 an if / else statement inside the while loop, which was incorrect.

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

Answer 2

The pop() method does not do what you think. You should read the Stack documentation .

Answer 3

In the published pseudocode, while is separated from 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 view in the first element in a while state.

Answer 4

Will there be 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(); }