Hilfe bei der Implementierung des Algorithmus All Nearest Smaller Values

Question

http://en.wikipedia.org/wiki/All_nearest_smaller_values . Dies ist der Ort des Problems und hier ist mein Code, aber ich habe einige Schwierigkeiten, ihn zu implementieren:

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

Und hier ist der Pseudo-Code von der Website:

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

Was ist mit meinem Code los?

Answer 1

その方法 pop() nicht das tut, was Sie denken. Sie sollten die [Stack Dokumentation](http://java.sun.com/j2se/1.4.2/docs/api/java/util/Stack.html#pop()) .

Answer 2

Hier ist der gleiche Pseudocode, aber ich habe Klammern hinzugefügt, damit Sie sehen können, wo jede Anweisung beginnt und endet.

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
}

Sie hatten die if/else-Anweisung innerhalb der while-Schleife, was nicht korrekt war.

Lesen Sie die Dokumentation des Stacks, um zu verstehen, was push , pop y peek tun, hier ist die Dokumentation: http://java.sun.com/j2se/1.4.2/docs/api/java/util/Stack.html

Answer 3

In dem geposteten Pseudocode wird die while ist getrennt von der if / else ; in Ihrem Java-Code die if befindet sich innerhalb der while .

Auch pop() beseitigt das oberste Element auf dem Stapel. Sie können es nicht verwenden, um das erste Element in der Bedingung von while .

Answer 4

Kann so etwas funktionieren?

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