Circular Arrays

August 26, 2016

Today’s exercise is to write a program that provides queues using a circular array. You should provide operations to make a new queue with a user-specified maximum size, determine if a queue is empty, add new elements to the end of the queue, and remove elements from the beginning of the queue.

Your task is to implement a queue as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “Circular Arrays”

  1. r. clayton said
    August 30, 2016 at 8:09 PM

    A solution in Racket.

  2. Daniel said
    August 31, 2016 at 11:49 PM

    Here’s a solution in Java.

    import java.util.NoSuchElementException;

public class Queue<T> {
  private T[] array;
  private int start = 0;
  private int count = 0;
  
  @SuppressWarnings("unchecked")
  public Queue(int size) {
    array = (T[])new Object[size];
  }
  
  public boolean add(T element) {
    if (count >= array.length) return false;
    array[(start+count) % array.length] = element;
    ++count;
    return true;
  }
  
  public T remove() {
    if (isEmpty()) throw new NoSuchElementException();
    T element = array[start];
    start = (start+1) % array.length;
    --count;
    return element;
  }
  
  public boolean isEmpty() {
    return count == 0;
  }
  
  public String toString() {
    StringBuffer sb = new StringBuffer("[");
    for (int i = 0; i < count; ++i) {
      if (i > 0) sb.append(", ");
      sb.append(array[(start + i) % array.length].toString());
    }
    sb.append("]");
    return sb.toString();
  }
  
  public static void main(String[] args) {
    Queue<Integer> queue = new Queue<>(3);
    queue.add(1);
    System.out.println(queue);
    
    queue.add(2);
    System.out.println(queue);
    
    queue.add(3);
    System.out.println(queue);
    
    queue.add(4); // queue is full, so won't add.
    System.out.println(queue);
    
    queue.remove();
    System.out.println(queue);
    
    queue.remove();
    System.out.println(queue);
    
    queue.remove();
    System.out.println(queue);
    
    try {
      queue.remove(); // queue is empty, so can't remove.
    } catch (NoSuchElementException e) {}
    
    queue.add(5);
    System.out.println(queue);
  }
}

    Output:

    [1]
[1, 2]
[1, 2, 3]
[1, 2, 3]
[2, 3]
[3]
[]
[5]

Leave a comment