我认为在调整数组大小时出现了问题,但在调整大小后队列未正确排队。这是我已经完成的类(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;
}
}
当我在调整大小后入队时,它会将一些数字放在前面而不是后面。
最佳答案
您的实现存在一些问题:
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()));
}
}
关于java - 循环数组支持的队列: enqueues at wrong offset after resizing,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30157629/