1

私は宿題の配列を使用してキューADTを実装しようとしています（リンクリストを使用するのは私次第でしたが、教授は私たちに新しいことや何かXDを学んでほしいと思っていると思います）。とにかく、私はキューの最後に要素を追加するメソッドに取り組んでいます。これと同じメソッドは、範囲外になった場合に新しいサイズ変更された配列を作成する必要があります。これは私が苦労しているメソッドです（ enqueue（）メソッド）。これが私のコードです：

import java.util.Arrays;


public class Queue<T> implements QueueInterface<T> {

    private T[] a;
    private int sz;

    public Queue(int capacity) {
        sz = 0;
        @SuppressWarnings("unchecked")
        T[] tempQueue = (T[])new Object[capacity];
        a= tempQueue;
    }

    public void enqueue(T newEntry) {
        try {
        for (int i=0; i<a.length; i++) {
                if (a[i] == null) {
                    a[i] = newEntry;
                    break;
                }
            }
        sz++;
        }
        catch (ArrayIndexOutOfBoundsException e) {
            @SuppressWarnings("unchecked")
            T[] tempQueue = (T[])new Object[a.length*+5];
            a= tempQueue;
            for (int i=0; i<a.length; i++) {
                if (a[i] == null) {
                    a[i] = newEntry;
                    break;
                }

            }
        }
    }

    public T dequeue() {
        T result = a[0];
        a[0] = null;
        for (int i=1; i<a.length;i++) {
            a[i-1] = a[i];
        }
        sz--;
        return result;
    }

    public T getFront() {
        return a[0];
    }

    public boolean isEmpty() {
        for (int i=0; i<a.length; i++) {
            if (a[i] != null) {
                return false;
            }
        }
        return true;
    }

    public void clear() {
        for (int i=0; i<a.length; i++) {
            a[i] = null;
            sz--;
        }
    }

    @Override
    public String toString() {
        return "Queue [a=" + Arrays.toString(a) + ", sz=" + sz + "]";
    }

}

みなさん、ありがとうございました!!!

4

5 に答える 5

2

配列を使用してキューを実装する場合、それを行う最良の方法は循環配列を使用することだと思います。そうすれば、すべての要素を1ステップ進める必要はありませんdequeue。ただし、サイズ変更可能な（制限付きの）キューを実装する必要があるため、循環配列の実装は少し難しくなります。ここにいくつかの便利なリンクがあります、

実装が必要な場合は、Googleだけで行ってください。

（これはあなたの質問に対する答えではないかもしれませんが、私はあなたの質問にコメントすることはできません。）

于 2012-11-04T23:45:08.997 に答える
1

配列の長さをチェックして、アウトバウンドを検出します-例外はコストがかかります。

アレイをコピーするには、適切なサイズの新しいアレイを作成してから、System.arrayCopyを使用します。

経験則では、サイズを一定量だけ大きくするのではなく、元のサイズのパーセンテージだけ大きくします（たとえば、30％大きくします）。

于 2012-11-04T23:39:12.153 に答える
0

サイズ変更ロジックを、または何かと呼ばれるプライベートメソッドに入れてみてくださいensureSize。そこで希望のサイズを確認してください。小さすぎる場合は、配列のサイズを変更して内容をコピーします。配列サイズを増やす必要がある可能性のあるメソッドからこのメソッドを呼び出します。

于 2012-11-04T23:29:23.390 に答える
0

配列を使用してキューを実装する最も効率的な方法ではないかもしれませんが、この方法で実装することにした場合、enqueueメソッドは必要以上に複雑になります。

sz最初の非nullを見つけるためにチェックするのではなく、新しいエントリを配置する必要がある場所を決定するために使用できるフィールドがあります。また、デキューが最後に移動した要素をクリアしていないため、null以外の検索はとにかく正しく機能しません。

このszフィールドには、例外によってその必要性を検出するのではなく、サイズ変更が必要な時期も示されます。

于 2012-11-04T23:30:22.343 に答える
0

Alan Kruegerの答えを補完する：サイズを変更するときに、配列全体を再度繰り返す必要はありません。古い配列の長さを格納する一時変数を作成し、そこから反復を開始します。

于 2012-11-04T23:33:15.663 に答える