java - 循环数组支持的队列: enqueues at wrong offset after resizing

Question

我认为在调整数组大小时出现了问题，但在调整大小后队列未正确排队。这是我已经完成的类(class)。

/**
* ArrayQueue
* Implementation of a queue using
* an array as the backing structure
*
* @author Your Name Here
* @version 1.0
*/
public class ArrayQueue<T> implements QueueADT<T> {

    // Do not add instance variables
    private T[] backing;
    private int size;
    private int front;
    private int back;

    /**
     * Construct an ArrayQueue with an
     * initial capacity of INITIAL_CAPACITY
     *
     * Use Constructor Chaining
     */
    public ArrayQueue() {
        backing = (T[]) new Object[INITIAL_CAPACITY];
        size = 0;
        front = 0;
        back = 0;
    }

    /**
     * Construct an ArrayQueue with the specified
     * initial capacity of initialCapacity
     * @param initialCapacity Initial capacity of the backing array.
     */
    public ArrayQueue(int initialCapacity) {
        backing = (T[]) new Object[initialCapacity];
        size = 0;
        front = 0;
        back = 0;
    }

    @Override
    public void enqueue(T data) {
        if (data == null) {
            throw new IllegalArgumentException("Data is null.");
        }
        //Resize
        if (size >= backing.length) {
            T[] backingCopy = (T[]) new Object[backing.length * 2];
            for (int i = 0; i < backing.length; i++) {
                backingCopy[i] = backing[i];
            }
            front = 0;
            back = backing.length - 1;
            backing = backingCopy;
        }
        backing[back] = data;
        back = (back + 1) % backing.length;
        size++;
    }

    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("Queue is empty.");
        }
        T returnData = backing[front];
        backing[front] = null;
        front = (front + 1) % backing.length;
        size--;
        return returnData;

    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Returns the backing array for your queue.
     * This is for grading purposes only. DO NOT EDIT THIS METHOD.
     *
     * @return the backing array
     */
    public Object[] getBackingArray() {
        return backing;
    }
}

当我在调整大小后入队时，它会将一些数字放在前面而不是后面。

Answer 1

您的实现存在一些问题:

A.调整数组大小后，您可以设置:

back = backing.length - 1;

应该是:

back = backing.length;

让我们以容量为1的队列为例:

• 创建队列初始容量1:大小 = 0，front = 0，back = 0
• 添加元素:size = 1, front = 0, back > = 1 % 1 = 0

• 添加另一个元素:size == backing.length

  a.创建 backingCopy 数组

  b.将 backing 元素复制到 backingCopy 数组

  c. back = backing.length - 1 = 1 - 1 = 0

  d.设置backing = backingCopy

  e. backing[back] = data(这会覆盖索引 0 处第一个添加的元素)

<小时/>

B.调整数组大小后将 front 设置为 0 似乎是一个问题，除非在复制到 backingCopy 数组时重新排序数据。

<小时/>

数组队列:

public class ArrayQueue<T> {
  private T[] backing;
  private int size;
  private int front;
  private int back;


  public ArrayQueue() {
    backing = (T[])new Object[INITIAL_CAPACITY];
    size = 0;
    front = 0;
    back = 0;
  }

  public ArrayQueue(int initialCapacity) {
    backing = (T[]) new Object[initialCapacity];
    size = 0;
    front = 0;
    back = 0;
  }

  public void enqueue(T data) {
    if (data == null) {
      throw new IllegalArgumentException("Data is null.");
    }
    if (size() == backing.length) {
      resize();
    }
    backing[back] = data;
    back = (back + 1) % backing.length;
    size++;
  }

  private void resize() {
    T[] backingCopy = (T[]) new Object[backing.length == 0 ? 1 : backing.length * 2];
    // Insert elements from backing array to backingCopy in order.
    System.arraycopy(backing, front, backingCopy, 0, backing.length - front);
    System.arraycopy(backing, 0, backingCopy, backing.length - front, back);
    front = 0;
    back = backing.length;
    backing = backingCopy;
  }

  public T dequeue() {
    if (isEmpty()) {
      throw new java.util.NoSuchElementException("Queue is empty.");
    }
    T returnData = backing[front];
    backing[front] = null;
    front = (front + 1) % backing.length;
    size--;
    return returnData;
  }

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size() == 0;
  }

  int front() {
    return front;
  }

  int back() {
    return back;
  }

  Object[] getBackingArray() {
    return backing;
  }

  static final int INITIAL_CAPACITY = 100;
}

ArrayQueue测试:

import org.junit.Test;

import java.util.Arrays;
import java.util.NoSuchElementException;

import static org.junit.Assert.*;


public class ArrayQueueTest {

  @Test
  public void enqueue_withInitialCapacity0() {
    // Given an ArrayQueue with initialCapacity 0.
    int initialCapacity = 0;
    ArrayQueue<Integer> q = new ArrayQueue<Integer>(initialCapacity);

    // When enqueue is called.
    q.enqueue(0);

    // Then ArrayQueue resizes backing array to 1 and adds element.
    assertEquals(Arrays.asList(0), Arrays.asList(q.getBackingArray()));
  }

  @Test
  public void enqueue_lessThanCapacity() {
    // Given an ArrayQueue with some initialCapacity.
    ArrayQueue<Integer> q = new ArrayQueue<Integer>(2);

    // When less than capacity elements are enqueued.
    q.enqueue(0);

    // Then ArrayQueue adds elements to backing array.
    assertEquals(Arrays.asList(0, null), Arrays.asList(q.getBackingArray()));
  }

  @Test
  public void enqueue_toCapacity() {
    // Given an ArrayQueue with some initialCapacity.
    ArrayQueue<Integer> q = new ArrayQueue<Integer>(2);

    // When initialCapacity elements are enqueued.
    q.enqueue(0);
    q.enqueue(1);

    // Then ArrayQueue adds elements to backing array.
    assertEquals(Arrays.asList(0, 1), Arrays.asList(q.getBackingArray()));
  }

  @Test
  public void enqueue_withResize() {
    // Given an ArrayQueue is at capacity.
    int initialCapacity = 2;
    ArrayQueue<Integer> q = new ArrayQueue<Integer>(initialCapacity);
    q.enqueue(0);
    q.enqueue(1);

    // When enqueue is called again.
    q.enqueue(2);

    // Then ArrayQueue is capacity is doubled and element is added.
    int expectedCapacity = 2 * initialCapacity;
    assertEquals(expectedCapacity, q.getBackingArray().length);
    assertEquals(Arrays.asList(0, 1, 2, null), Arrays.asList(q.getBackingArray()));
  }

  @Test(expected = NoSuchElementException.class)
  public void dequeue_isEmpty() {
    // Given an empty ArrayQueue.
    ArrayQueue<Integer> q = new ArrayQueue<Integer>();

    // Throws when dequeue is called.
    q.dequeue();
    fail("Should have thrown NoSuchElementException.");
  }

  @Test
  public void dequeue() {
    ArrayQueue<Integer> q = new ArrayQueue<Integer>(4);
    q.enqueue(0);
    q.enqueue(1);
    q.enqueue(2);

    assertEquals(3, q.size());
    assertEquals(0, q.front());
    assertEquals(3, q.back());
    assertEquals(Arrays.asList(0, 1, 2, null), Arrays.asList(q.getBackingArray()));

    assertEquals(0, (int) q.dequeue());
    assertEquals(2, q.size());
    assertEquals(1, q.front());
    assertEquals(3, q.back());
    assertEquals(Arrays.asList(null, 1, 2, null), Arrays.asList(q.getBackingArray()));

    assertEquals(1, (int) q.dequeue());
    assertEquals(1, q.size());
    assertEquals(2, q.front());
    assertEquals(3, q.back());
    assertEquals(Arrays.asList(null, null, 2, null), Arrays.asList(q.getBackingArray()));

    assertEquals(2, (int) q.dequeue());
    assertEquals(0, q.size());
    assertEquals(3, q.front());
    assertEquals(3, q.back());
    assertEquals(Arrays.asList(null, null, null, null), Arrays.asList(q.getBackingArray()));
  }

  @Test
  public void loopAround_enqueue() {
    // Given an ArrayQueue with elements that have been dequeued.
    ArrayQueue<Integer> q = new ArrayQueue<Integer>(4);
    q.enqueue(0);
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.dequeue();
    q.dequeue();

    assertEquals(2, q.size());
    assertEquals(2, q.front());
    assertEquals(0, q.back());
    assertEquals(Arrays.asList(null, null, 2, 3), Arrays.asList(q.getBackingArray()));

    // When enqueue is called.
    q.enqueue(4);
    q.enqueue(5);

    // Then resize is not called and elements are added to the front beginning of the array.
    assertEquals(4, q.size());
    assertEquals(2, q.front());
    assertEquals(2, q.back());
    assertEquals(Arrays.asList(4, 5, 2, 3), Arrays.asList(q.getBackingArray()));
  }


  @Test
  public void loopAround_enqueue_withResize() {
    // Given an ArrayQueue that loops around and is at capacity.
    ArrayQueue<Integer> q = new ArrayQueue<Integer>(4);
    q.enqueue(0);
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.dequeue();
    q.dequeue();
    q.enqueue(4);
    q.enqueue(5);
    assertEquals(Arrays.asList(4, 5, 2, 3), Arrays.asList(q.getBackingArray()));

    // When enqueue is called.
    q.enqueue(6);

    // Then ArrayQueue resizes and reorders the backing array before adding the element.
    assertEquals(5, q.size());
    assertEquals(0, q.front());
    assertEquals(5, q.back());
    assertEquals(Arrays.asList(2, 3, 4, 5, 6, null, null, null), Arrays.asList(q.getBackingArray()));
  }

  @Test
  public void loopAround_dequeue() {
    ArrayQueue<Integer> q = new ArrayQueue<Integer>(4);
    q.enqueue(0);
    q.enqueue(1);
    q.enqueue(2);
    q.dequeue();
    q.enqueue(3);
    q.enqueue(4);

    assertEquals(4, q.size());
    assertEquals(1, q.front());
    assertEquals(1, q.back());
    assertEquals(Arrays.asList(4,1,2,3), Arrays.asList(q.getBackingArray()));

    assertEquals(1, (int) q.dequeue());
    assertEquals(3, q.size());
    assertEquals(2, q.front());
    assertEquals(1, q.back());
    assertEquals(Arrays.asList(4, null, 2, 3), Arrays.asList(q.getBackingArray()));

    assertEquals(2, (int) q.dequeue());
    assertEquals(2, q.size());
    assertEquals(3, q.front());
    assertEquals(1, q.back());
    assertEquals(Arrays.asList(4, null, null, 3), Arrays.asList(q.getBackingArray()));

    assertEquals(3, (int) q.dequeue());
    assertEquals(1, q.size());
    assertEquals(0, q.front());
    assertEquals(1, q.back());
    assertEquals(Arrays.asList(4, null, null, null), Arrays.asList(q.getBackingArray()));

    assertEquals(4, (int) q.dequeue());
    assertEquals(0, q.size());
    assertEquals(1, q.front());
    assertEquals(1, q.back());
    assertEquals(Arrays.asList(null, null, null, null), Arrays.asList(q.getBackingArray()));
  }
}