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

2 Responses to “Circular Arrays”

  1. r. clayton said

    A solution in Racket.

  2. Daniel said

    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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: