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

在入队期间，您首先将 +1 添加到前面，然后设置对象，但您需要以相反的顺序进行操作。

另一方面，实现自己的 Queue 类是一个非常糟糕的主意（除非您这样做是为了学习），因为 Java 已经为此提供了一个高速、可靠且经过良好测试的类。您可以查看 Java 队列类的源代码，了解如何正确执行此操作。

于 2013-10-12T18:37:56.520 回答
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的是 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

我认为您的意思如下（尽管您的整体理性是正确的）

更正

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

而不是您的示例（因为 % 运算符具有更高的优先顺序，相当于从左到右的乘法或除法）：

(0 + 1 % 3) = 1  => 1
(1 + 1 % 3) = 2  => 2
(2 + 1 % 3) = 0  => 3
于 2015-09-10T00:59:50.143 回答