1

リンクされたリスト スタイルのスタックを Java で実装しようとしています (組み込みの明白な方法を使用せずに)。プッシュ操作は簡単ですが、ポップ操作は面倒です。「ポップされた」値を呼び出し元に返し、同時にリンクされたリストを調整すると便利であることは明らかですが、これはうまくいかないようです。

public class ListElement {

/* constructor */
public ListElement(Integer data) {
    value = data;
}

/* next pointer and the data */
private ListElement next;
private Integer value;

/* gets the next element */
public ListElement getNext() {
    return next;
}

/* gets the data */
public Integer getValue() {
    return value;
}

/* sets the next element */
public void setNext(ListElement elem) {
    next = elem;
}

/* sets the data */
public void setValue(Integer data) {
    value = data;
}

/* prints out the list */
public void printList(ListElement head) {
    String listString = "";
    ListElement elem = head;
    while (elem != null) {
        listString = listString + elem.getValue().toString() + " ";
        elem = elem.getNext();
    }
    System.out.println(listString);
}

/* inserting at the front */
public ListElement push(ListElement head, Integer data) {
    ListElement elem = new ListElement(data);
    elem.setNext(head);
    return elem;
}

/* pop the first element */
public Integer pop (ListElement head){
    Integer popped = head.getValue();
    head = head.getNext();

    return popped;
}

 public static void main(String[] args) {



    System.out.println("Constructing List with 2 ...");
    ListElement myList = new ListElement(2);
    myList.printList(myList);

    System.out.println("Adding 1 to beginning ...");
    myList = myList.push(myList, 1);
    myList.printList(myList);

    System.out.println("Adding 0 to beginning ...");
    myList = myList.push(myList, 0);
    myList.printList(myList);

    System.out.println("Pop ...");
    Integer popped =  myList.pop(myList);
    System.out.println("Value is " + popped);
    myList.printList(myList);
      }

 }
4

4 に答える 4

2

通常、あなたのような構造には 2 つのクラスがあり、1 つは で、もう 1 つはListElementですList。StackElement名前はとの方がいいと思いますが、先に進みStackます....

問題は、あなたが疑うように、Java が pop メソッドにあることです。

/* pop the first element */
public Integer pop (ListElement head){
    Integer popped = head.getValue();
    head = head.getNext();
    return popped;
}

しかし、メインメソッドでも：

System.out.println("Pop ...");
Integer popped =  myList.pop(myList);

ここでの問題は、myList がメソッドhead.getNext()内の改訂された値で更新されることを期待していることですpop()。

これは発生しません.... Java は、myList呼び出し時にへの別の「参照」を作成しpop()、回線head = head.getNext()が を変更しませmyListんpop()。

この状況は通常、2 番目のクラスで解決されます。「リスト」と呼びます (または、私が言うように、そうである必要がありますStack)...

public class Stack() {
    private StackElement head = null;
    public push(Integer value) {
        StackElement topush = new StackElement(value);
        topush.setNext(head);
        head = topush;
    }
    public Integer pop() {
        StackElement topop = head;
        if (head != null) {
            head = topop.getNext();
            return topop.getValue();
        }
        return null;
    }
}

次に、メイン メソッドで、この新しい Stack クラスを使用する必要があります。

Stack stack = new Stack();
stack.push(2);
....
于 2013-11-11T05:03:05.267 に答える
1

あなたが言うとき、あなたはmyListを変更していません

head = head.getNext();

pop メソッドでローカル変数を変更しているだけです。

私のお気に入りの解決策は、'List' と 'Element' を 2 つの別々のファイルのように完全に分離することです。そうすれば、物事はより理にかなっているはずです。

リスト

  • head (要素型)

エレメント

  • 次へ (Element 型)
  • 値 (整数型)
于 2013-11-11T04:57:53.297 に答える
1

通常、このようなリンク リストでは、スタックのトップへの参照を含む Header または LinkedList クラスが必要です。

1 つのフィールドListElement topと関数popと を持ちpushます。

pushご想像のとおり、 start を新しい ListElement に設定するだけで、その要素nextは古いstart.

popstart要素の値と設定を返すだけなstart = start.getNext()ので、上部が削除されます。

于 2013-11-11T04:56:49.653 に答える
1

ここで適切な実装を見つけることができます。

あなたのコードで間違っているのは次のとおりです。

/* pop the first element */
public Integer pop (ListElement head){
    Integer popped = head.getValue();
    head = head.getNext();
    return popped;
}

head関数に対してのみローカルな要素を変更します。

コードを 2 つのクラスに分割する必要があります。

  • ListElement : 値/次の情報のみが含まれます。

    public class ListElement {
     ListElement next;
     Integer value;
}

  • LinkedStack : 少なくともスタック関数 (プッシュ/ポップ) と、スタックの最初の ListElement への参照のみが含まれます。pop 関数の呼び出し中に更新する必要があるのは、この参照です。

    public class LinkedStack {

     private ListElement first;

     public void push(Integer item) {
         ListElement oldfirst = first;
         first = new ListElement();
         first.value= item;
         first.next = oldfirst;
     }


     public Integer pop() {
         Integer item = first.value;      
         first = first.next;           
         return item;                 
     }
}
于 2013-11-11T05:03:12.910 に答える