Circular array-backed queue: enqueues at wrong offset after resizing

Question

I think something is wrong when I'm resizing the array, but the queue isn't enqueuing correctly after I resize. This was for a class I'm already done with.

/**
* 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;
    }
}

When I enqueue after the resizing, it puts some numbers at the front instead of the back.

dting · Accepted Answer · 2015-05-12 02:53:32Z

There are a few problems with your implementation:

A. After you resize the array, you set:

back = backing.length - 1;

that should be:

back = backing.length;

Let's take the example of an queue with capacity 1:

create queue initial capacity 1: size = 0, front = 0, back = 0
add an element: size = 1, front = 0, back = 1 % 1 = 0
add another element: size == backing.length

a. create backingCopy array

b. copy over backing elements to backingCopy array

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

d. set backing = backingCopy

e. backing[back] = data (this overwrites the first added element at index 0)

B. Setting front to 0 after resizing the array seems like a problem unless you reorder the data when copying to the backingCopy array.

ArrayQueue:

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;
}

ArrayQueueTest:

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()));
  }
}

In the capacity-1 example, enqueue will set back to 0 (not 1) immediately after adding the first element, since (back + 1) % backing.length will mean 1 % 1. (This is actually not a bug. There are two states where front and back should be equal: when the buffer is empty, and when it is full.) On the second enqueue, the resizing will set back to 0 again, but for a completely different reason, just as you said. It should set back = backing.length, with no - 1 on the end... assuming he fixes the ordering problem you and Bubletan pointed out.

Bubletan · Accepted Answer · 2015-05-11 12:20:24Z

1

If back < front, you will copy the array incorrectly. You should copy both from front to the end and from the beginning to back.

I haven't tested, but I think this should work:

if (back < front) {
    System.arraycopy(backing, front, backingCopy, 0, backing.length - front);
    System.arraycopy(backing, 0, backingCopy, backing.length - front, back);
} else {
    System.arraycopy(backing, 0, backingCopy, 0, backing.length);
}

Also, you have to set back to backing.length instead of backing.length - 1.

edited May 11, 2015 at 12:20

answered May 10, 2015 at 23:48

Bubletan

3,8636 gold badges27 silver badges33 bronze badges

3 Comments

Germann Arlington Over a year ago

What you suggested will copy existing data correctly but it will not fix the problem as described

Kevin J. Chase Over a year ago

I agree (based on how he sets front and back) that this is what he wants his resize operation to do.

Bubletan Over a year ago

I see, there's (at least) one more mistake, edited the answer.

Germann Arlington · Accepted Answer · 2015-05-10 23:38:07Z

-1

Look closely at what happens after you resize (copy) your backing array...

Better still consider RingBuffer - you can find it on Google

answered May 10, 2015 at 23:38

Germann Arlington

3,3532 gold badges19 silver badges21 bronze badges

Collectives™ on Stack Overflow

Circular array-backed queue: enqueues at wrong offset after resizing

3 Answers 3

1 Comment

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related