0

配列ベースのデキューを作成しようとしていますが、出力の順序が正しくありません。現在は制限付きですが、デキューを正しく機能させる方法を理解したら、おそらく無制限を使用するでしょう。

これが私のコードです：

public class ArrayBndDequeue<T> implements BoundedDequeueInterface<T>
{
  protected final int DEFCAP = 100; // default capacity
  protected T[] queue;              // array that holds queue elements
  protected int numElements = 0;    // number of elements n the queue
  protected int front = 0;          // index of front of queue
  protected int rear;               // index of rear of queue

  public ArrayBndDequeue() 
  {
    queue = (T[]) new Object[DEFCAP];
     rear = DEFCAP - 1;
  }

  public ArrayBndDequeue(int maxSize) 
  {
    queue = (T[]) new Object[maxSize];
     rear = maxSize - 1;
  }

  public void enqueue(T element)
  // Throws QueueOverflowException if this queue is full;
  // otherwise, adds element to the front of this queue.
  {  
    if (isFull())
      throw new DequeueOverflowException("Enqueue attempted on a full queue.");
    else
    {
      front = (front + 1) % queue.length;
      queue[front] = element;
      numElements = numElements + 1;
    }
  }

  public T dequeue()
  // Throws QueueUnderflowException if this queue is empty;
  // otherwise, removes rear element from this queue and returns it.
  {   
    if (isEmpty())
      throw new DequeueUnderflowException("Dequeue attempted on empty queue.");
    else
    {
      T toReturn = queue[rear];
      queue[rear] = null;
      rear = (rear + 1) % queue.length;
      numElements = numElements - 1;
      return toReturn;
    }
  }

  public boolean isEmpty()
  // Returns true if this queue is empty; otherwise, returns false
  {              
    return (numElements == 0);
  }

  public boolean isFull()
  // Returns true if this queue is full; otherwise, returns false.
  {              
    return (numElements == queue.length);
  }
}

そして、これは私のメインクラスです:

public class Dequeue
{
    public static void main(String[] args)
    {
        Scanner userInput = new Scanner(System.in);
        String line;

        BoundedDequeueInterface<String> queue;
        queue = new ArrayBndDequeue<String>(3);

        for (int i = 1; i <= 3; i++)
        {
            System.out.print("Enter a line of text > ");
            line = userInput.nextLine();
            queue.enqueue(line);
        }

        System.out.println("\nOrder is:\n");

        while (!queue.isEmpty())
        {
            line = queue.dequeue();
            System.out.println(line);
        }
    }
}

プログラムを実行するときは、通常、次のように入力します。

1
2
3

出力は次のようになります。

2
3
1

何か助けはありますか？私のコードがもう必要な場合は、お知らせください。

4

3 に答える 3

0

あなたが説明する問題は、挿入中の次の式に起因します（削除にも同様に適用されます）：

this.front = (this.front + 1) % this.queue.length;

これは次のように評価されます。

  1. (0 + 1 % 3) = 1
  2. (1 + 1 % 3) = 2
  3. (2 + 1 % 3) = 0

3 番目の値が格納されるため、キューのサイズが 3 であるため、取得3 % 3する値は 0 です。したがって、値はインデックス 0 に格納されます。

JDK の ArrayDeque でこのアルゴリズムの定義を見てください。彼らは次のようにします：

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}
于 2013-10-12T18:56:41.640 に答える
0

エンキュー中に、最初に+1を前に追加してからオブジェクトを設定しますが、逆の順序で行う必要があります。

一方、独自の Queue クラスを実装することは非常に悪い考えです (もちろん、学習のために実装する場合を除きます)。Java には、このための高速で信頼性が高く、十分にテストされたクラスが既にあるためです。適切に実行する方法については、Java キュー クラスのソース コードを参照してください。

于 2013-10-12T18:37:56.520 に答える