Помощь в реализации алгоритма Все Ближайшие Меньшие Значения

Question

http://en.wikipedia.org/wiki/All_nearest_smaller_values. Это сайт проблемы и вот мой код, но у меня есть некоторые проблемы с его реализацией:

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);
                }
            }
        }
    }
}

А вот и псевдокод с сайта:

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

Что случилось с моим кодом?

Answer 1

Метод pop() не делает то, что вы думаете, он делает. Вам следует прочитать документацию Stack .

Answer 2

В размещенном псевдокоде while отделен от if / else; в вашем коде Java if находится внутри while.

Также pop() удаляет верхний элемент стека. Вы не можете использовать его для просмотра первого элемента в состоянии while.

Answer 3

Здесь тот же псевдокод, но я добавил скобки, чтобы вы могли видеть, где начинается и заканчивается каждый оператор.

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
}

В цикле while был оператор if / else, который был неверным.

Проверьте документацию стека, чтобы понять, что push, pop и peek делают, вот документация: http://java.sun.com/j2se/1.4.2/docs/api/java/util/Stack.html

Answer 4

Будет ли что-то подобное работать?

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