0

そのため、キューを 1 つだけ使用してスタックを実装しようとしましたが、動作しているように見えますが、オンラインで見たソリューションのほとんどが 2 つのキューを使用しているため、何か問題があるかどうかはわかりません。私の実装に問題があるかどうか、誰か教えてもらえますか?

public class MyStack<T> {

/**
 * @param args
 */
private Queue<T> q = new LinkedList<T>();
public MyStack(){
}
public static void main(String[] args) {
    // TODO Auto-generated method stub
    MyStack<String> s = new MyStack<String>();
    s.push("1");
    s.push("2");
    s.push("3");
    s.push("4");
    System.out.println(s.pop());
    System.out.println(s.pop());
    System.out.println(s.pop());
    System.out.println(s.pop());
    System.out.println(s.pop());
}

public void push(T s){
    q.offer(s);         
}

public T pop(){
    int n = q.size();
    for(int i = 0; i < n-1; i++){
        q.offer(q.poll());              
    }
    return q.poll();
}
}

出力:
4
3
2
1
null

4

4 に答える 4

1

StackまたはDequeまたはLinkedListのいずれかを使用する必要があります。

独自の実装は...無意味です。もちろん（@basが示唆するように）データ構造のコースを行っている場合を除き、コマンドーに移動して独自の構造を最初から実装する必要があります。あなたが作ろうとしているものに似ているため、別の構造を使用することは、ネジでハンマーを使用するようなものです.

本当に自分で何かを実装する必要がある場合は、次のようなものが機能するはずです。

public class Stack<T> {
  private Entry top = null;

  private class Entry {
    final Entry up;
    final T it;

    public Entry(Entry up, T it) {
      this.up = up;
      this.it = it;
    }
  }

  public void push ( T it ) {
    top = new Entry(top, it);
  }

  public T pop () {
    if ( top == null ) {
      throw new EmptyStackException();
    }
    T it = top.it;
    top = top.up;
    return it;
  }
}

注意: これはスレッドセーフではない可能性があります。

于 2013-08-04T21:23:41.793 に答える
1

スタックから何かをポップするたびにスタック全体をループする必要があるため、ソリューションは非効率的です。(事実上、最後にあった要素を削除する前に、リンクされたリスト全体をトラバースする必要があります。) 編集: Java のリンクされたリストはとにかく二重にリンクされているため、これはまったく無意味です。

于 2013-08-04T21:28:05.837 に答える
0

スタックが 2 つのキューを使用する理由はまったくありません。実際のところ、その下のノードを参照する 1 つのトップ ノードを追跡するだけで済みます。

コードは機能しているように見えますが、nachokk が言ったように、これはコード レビュー用のサイトではありません。このサイトは、エラーが発生してサポートが必要な場合に役立ちます。

于 2013-08-04T21:23:07.330 に答える
0

エンキューやデキューなどの基本的なキュー操作がある場合にのみ、2 つのキューを使用する必要があります。他の方法を使用できる場合、特にキューを反復処理する場合は、1 つのキューだけで実行できます。

于 2013-08-04T22:01:48.320 に答える