Stack-Implementierung mithilfe einer verknüpften Liste

107523
Arun Prakash

Um das Konzept zu verstehen, habe ich die Stack-Operationen mit einer verknüpften Liste implementiert. Bitte überprüfen Sie den Code und teilen Sie mir Ihre Vorschläge mit.

Node.java

public class Node {

public int data;
public Node next;

public Node(int data) {
    this.data = data;
}

public void displayNode() {
    System.out.print(data);
    System.out.print("  ");

 }
}

LinkList.java

public class LinkList {

private Node first = null;

public void insertFirst(int data) {
    Node n = new Node(data);
    n.next = first;
    first = n;
}

public Node deleteFirst() {
    Node temp = first;
    first = first.next;
    return temp;
}

public void displayList() {
    Node current = first;
    while (current != null) {
        current.displayNode();
        current = current.next;
    }
}

public boolean isEmpty() {
    return (first == null);
  }
}

LinkListStack.java

public class LinkListStack {

LinkList li = new LinkList();

public void push(int data) {
    li.insertFirst(data);
}

public void pop() {
    while(!li.isEmpty()){
    li.deleteFirst();
    }
}

public void displayStack() {
    System.out.println("  ");
    li.displayList();
  }
}

LinkListStackDemo.java

public class LinkListStackDemo {

public static void main(String[] args) {
    LinkListStack st = new LinkListStack();

    st.push(50);
    st.push(70);
    st.push(190);
    st.displayStack();
    st.pop();
    st.displayStack();

  }
 }
Antworten
10
Bitte ändern Sie die while-Bedingung nicht in eine if-Bedingung in Ihren Änderungen, diese wurden in Antworten angesprochen. [Was Sie nach dem Erhalt von Antworten tun können und was nicht] (http://meta.codereview.stackexchange.com/a/1765) rolfl vor 5 Jahren 0

3 Antworten auf die Frage

18
janos

Zeitliche Komplexität

Die zeitliche Komplexität von Push- und Pop-Vorgängen sollte \ $ O (1) \ $ sein. Dies ist auch in Ihrem Fall der Fall. Es ist egal, wie viele Elemente Sie haben, diese Vorgänge sollten konstant dauern. (UPDATE: Sie haben Ihren ursprünglichen Beitrag bearbeitet und popden gesamten Stapel gelöscht. Dies ist nicht normal! Normalerweise sollte der popVorgang auf einem Stapel den letzten Mehrwert liefern. Dies ist \ $ O (1) \ $ time.)

Vermeiden Sie das Drucken auf stdout

Anstelle der display*Methoden, für die gedruckt wird, stdoutist es besser, sie zu überschreiben toString. Auf diese Weise wäre Ihre Implementierung testbarer.

Verallgemeinern

Warum sollte der Stack, die verknüpfte Liste und die Knotenelemente auf den intTyp beschränkt werden? Es wäre trivial einfach, umzuschreiben, damit es mit jedem Typ funktioniert T.

Die Frage ist mit "Anfänger" gekennzeichnet. Ich verstehe, dass Sie mit Generika noch nicht vertraut sind. In diesem Fall finden Sie dieses offizielle Tutorial . Oder Sie können vielleicht auch von meiner Beispielimplementierung weiter unten lernen.

Fügen Sie eine isEmptyMethode für den Stapel hinzu

Ihre verknüpfte Liste hat eine isEmptyMethode, der Stack jedoch nicht. Es wäre gut, eine solche Methode auch für den Stapel zu haben.

Das Rad neu erfinden

Wenn Sie das Rad neu erfinden (hier die verknüpfte Liste), ist es gut, das Vorhandene zu imitieren. Zum Beispiel java.util.LinkedListverwendet die Methode Namen addFirstund removeFirst, statt insertFirstund deleteFirst. Es ist gut, dem Beispiel zu folgen.

Zugriffsmodifizierer und Kapselung

Wie @rolfl hervorgehoben hat, Nodesollte es nicht nach außen exponiert werden. Benutzer des Stapels sollten nicht wissen, wie er funktioniert.

Die Mitglieder von Nodesollten auch privat sein und die dataund nextFelder können sein final. In ähnlicher Weise sollte das Mitglied der verknüpften Liste privat im Stapel sein.

Benennung

Sie verwenden an vielen Stellen schlechte Namen.

  • Statt nfür den neuen Knoten beim Ersetzen des ersten Elements einer verknüpften Liste newFirstwäre das intuitiver
  • Statt tempfür das alte erste Element, das aus einer verknüpften Liste entfernt wurde, oldFirstwäre es intuitiver
  • Anstelle von lifür die verknüpfte Liste im Stapel linkedListwäre das intuitiver

Vorgeschlagene Implementierung

class LinkList<T> {

    private static class Node<T> {

        private final T data;
        private final Node<T> next;

        public Node(T data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    private Node<T> first = null;

    public void addFirst(T data) {
        Node<T> newFirst = new Node<T>(data);
        newFirst.next = first;
        first = newFirst;
    }

    public T removeFirst() {
        Node<T> oldFirst = first;
        first = first.next;
        return oldFirst.data;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node current = first;
        while (current != null) {
            builder.append(current).append(" ");
            current = current.next;
        }
        return builder.toString();
    }

    public boolean isEmpty() {
        return first == null;
    }

}

class LinkListStack<T> {

    private final LinkList<T> linkedList = new LinkList<>();

    public void push(T data) {
        linkedList.addFirst(data);
    }

    public T pop() {
        return linkedList.removeFirst();
    }

    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public String toString() {
        return linkedList.toString();
    }
}

Unit-Tests

@Test
public void testPushAndPop() {
    LinkListStack<Integer> st = new LinkListStack<>();
    st.push(50);
    st.push(70);
    st.push(190);
    assertEquals("190 70 50", st.toString());
    assertEquals(190, (int) st.pop());
    assertEquals("70 50", st.toString());
}

@Test
public void testPopUntilEmpty() {
    List<Integer> values = Arrays.asList(50, 70, 190, 20);
    LinkListStack<Integer> st = new LinkListStack<>();
    assertTrue(st.isEmpty());
    for (Integer value : values) {
        st.push(value);
    }
    assertFalse(st.isEmpty());
    for (int i = values.size(); i > 0; --i) {
        assertEquals(values.get(i - 1), st.pop());
    }
    assertTrue(st.isEmpty());
}
8
rolfl

Nun, es gibt ein paar Dinge, die man hier durchmachen muss.

Knoten

Beginnend mit der Node-Klasse. Dies sollte nicht öffentlich sein. Es gibt keinen Grund für Sie, die Logik einer anderen Klasse als der LinkedList-Klasse auszusetzen. Es ist üblich, die Node-Klasse als statische innere Klasse der Datenstruktur einzuschließen. So etwas wie:

public class LinkList {

    private static class Node {

        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }

        void displayNode() {
            System.out.print(data);
            System.out.print("  ");

        }

    }

    private Node first = null;

    ...

Komplexität

Sie behaupten, dass die Komplexität für Push und Pop \ $ O (n) \ $ ist, dies ist jedoch nicht der Fall. Beide Operationen betreffen nur den Kopf der Liste, zB:

public void insertFirst(int data) {
    Node n = new Node(data);
    n.next = first;
    first = n;
}

Infolgedessen handelt es sich um \ $ O (1) \ $ -Operationen, und das würde ich für eine verknüpfte Liste, die am Kopf eingefügt wird, erwarten.

LinkedList

Die deleteFirst-Methode sollte keinen Node-Wert zurückgeben. Es sollte das 'Spiegelbild' der Einfügemethode sein. Die insert-Methode fügt ein ein int, und die delete-Methode sollte auch ein zurückgeben int.

LinkedListStack

pop()Methoden sollten den gepoppten Wert zurückgeben. Deine gibt nichts zurück, es ist nichtig. Das ist nicht normal.

Hinweis: Es wurde darauf hingewiesen, dass Ihre Pop-Methode aufgrund der while (!isEmpty())Schleife alle Werte aus der Liste entfernt . Diese Schleife wurde hinzugefügt, nachdem ich diesen Teil der Antwort geschrieben hatte (aber bevor ich auf "Senden" geklickt hatte). Der Satz, den ich oben habe, ist für eine klassische "Pop" -Methode genau, die den ersten Wert aus dem Stack entfernt (und in Java und vielen anderen Sprachen auch diesen Wert zurückgibt).

Was Sie jetzt haben, ist schlimmer, Sie haben eine Methode namens "Pop", die nichts dergleichen tut, es ist eine "Clear" -Methode, sie leert den Stapel. Als Ergebnis haben Sie überhaupt keinen Stack. Sie haben eine Klasse namens Stack, die kein Stack ist. In vielen Fällen ist es WOM (Write Only Memory), Sie können Werte in den Stack schreiben, aber niemals lesen.

Zusammenfassung

Ihre Einrückung ist aus. Ich vermute, dies liegt daran, dass Sie mit dem Markierungssystem von Code Review nicht vertraut sind. Sie sollten Ihren Code in das Bearbeitungsfeld einfügen, dann alles auswählen und dann ctrl- drücken k.

`pop ()` nichts zurückzugeben ist in Java nicht normal, meinst du? In C ++ ist das normal. Jamal vor 5 Jahren 0
@Jamal Vielleicht, weil C ++ versucht, jeden Bruchteil einer Nanosekunde zu retten, was die Rückgabe eines ungenutzten Wertes kosten könnte. Es könnte tatsächlich kostspielig sein, wenn ein großes Objekt kopiert werden soll und der Compiler nicht garantiert, dass er es weglassen kann. Das kann in Java nicht passieren. Es ist traurig, dass die Java Collection nicht mehr von STL inspiriert ist. maaartinus vor 5 Jahren 2
Beachten Sie, dass pop () eine while-Schleife ist. Es gibt nicht nur nichts zurück, sondern zerstört auch den gesamten Stapel. raptortech97 vor 5 Jahren 0
@ raptortech97 - du hast recht, aber [es war nicht, als ich die frage zuerst beantwortete] (http://codereview.stackexchange.com/revisions/62710/1) .... aber ich sehe, dass er seine redaktion bekam Kurz bevor ich meine Antwort bekommen habe, können wir sie stehen lassen. rolfl vor 5 Jahren 0
@ raptortech97 - das macht das Problem noch schlimmer, ich habe in meiner Antwort einen Hinweis hinzugefügt. rolfl vor 5 Jahren 0
@maaartinus - Der Grund, warum "pop" ein Objekt in C ++ nicht zurückgibt, ist, dass das Zurückgeben eines Objekts es kopiert und das Kopieren eine Ausnahme auslösen kann. In diesem Fall ist das Objekt verloren gegangen. Pete Becker vor 5 Jahren 1
@PeteBecker Thx, das macht Sinn. Also sollen die Armen die "Top" machen, richtig? Aber wenn eine Ausnahme in "top" erscheint, was soll ich tun? maaartinus vor 5 Jahren 0
@maaartinus - ja, rufen Sie "top" an, um das Objekt zu erhalten. top gibt keine Ausnahme aus: Es wird eine Referenz zurückgegeben. Wenn Sie dieses Objekt kopieren und die Kopie eine Ausnahme auslöst, ist der Stapel noch intakt, sodass Sie nichts verloren haben. Im schlimmsten Fall rufen Sie "Pop" an, um den Unruhestifter loszuwerden. Pete Becker vor 5 Jahren 1
@maaartinus - keine abweichenden Aussagen erforderlich. Es gibt viele, die auch über Java gemacht werden könnten, aber das ist weder produktiv noch angemessen. Pete Becker vor 5 Jahren 0
3
Franki

Warum schreibst du?

public void pop() {
    while(!li.isEmpty()){
    li.deleteFirst();
    }
}

anstatt

public void pop() {
    if(!li.isEmpty()){
    li.deleteFirst();
    }
}

weil das, was Sie geschrieben haben, pop()alle Elemente aus dem Stapel springt, anstatt eins. Oder irre ich mich?

Das ist nicht wirklich eine Antwort. Tatsächlich hat es am Ende eine Frage. Bitte ändern Sie dies, um der Struktur einer Antwort genauer zu folgen. Boris the Spider vor 5 Jahren 0