Circular Arrays

August 26, 2016

The circular array is stored in a vector q with indices of the start and end positions. An auxiliary variable size keeps track of the current number of elements in the array, so it can easily be determined if the array is empty or full:

(define (make-queue n)
  (let ((q (make-vector n #f))
        (start 0) (end 0) (size 0))
    (lambda (command . args)
      (case command
      ((empty?) (zero? size))
      ((enqueue)
        (if (= n size)
            (error 'enqueue "Full")
            (begin
              (set! size (+ size 1))
              (vector-set! q end (car args))
              (set! end (modulo (+ end 1) n)))))
      ((dequeue)
        (if (zero? size)
            (error 'enqueue "Empty")
            (let ((x (vector-ref q start)))
              (set! size (- size 1))
              (vector-set! q start #f)
              (set! start (modulo (+ start 1) n))
              x)))))))

Here are some examples:

> (set! q (make-queue 3))
> (q 'enqueue 1)
> (q 'enqueue 2)
> (q 'enqueue 3)
> (q 'enqueue 4)
Exception in enqueue: Full
Type (debug) to enter the debugger.
> (q 'dequeue)
1
> (q 'dequeue)
2
> (q 'dequeue)
3
> (q 'empty?)
#t
> (q 'dequeue)
Exception in enqueue: Empty
Type (debug) to enter the debugger.

Although it’s not a circular array, the normal Scheme implementation of a queue uses two lists, a front list in normal order and a back list in reverse order; new items are consed to the back list, the next item is popped from the head of the front list, and the back list is reversed to become the front list whenever the front list is exhausted. Thus, a queue containing the first five integers, in order, might look like ((1 2) 5 4 3) or ((1 2 3) 5 4) or ((1 2 3 4 5)) or (() 5 4 3 2 1). Here is a Scheme-ly queue, implemented as an abstract data type:

(define (make-queue)
  (let ((q (cons (list) (list)))) ; front/back
    (lambda (command . args)
      (case command
      ((empty?)
        (and (null? (car q)) (null? (cdr q))))
      ((enqueue)
        (set-cdr! q (cons (car args) (cdr q))))
      ((dequeue)
        (cond ((pair? (car q))
                (let ((x (caar q)))
                  (set-car! q (cdar q))
                  x))
        (else (set-car! q (reverse (cdr q)))
              (set-cdr! q (list))
              (if (null? (car q))
                  (error 'dequeue "Empty")
                  (let ((x (caar q)))
                    (set-car! q (cdar q))
                    x)))))))))

Here are some examples:

> (set! q (make-queue))
> (q 'empty?)
#t
> (q 'enqueue 1)
> (q 'enqueue 2)
> (q 'empty?)
#f
> (q 'dequeue)
1
> (q 'enqueue 3)
> (q 'enqueue 4)
> (q 'dequeue)
2
> (q 'dequeue)
3
> (q 'dequeue)
4
> (q 'dequeue)
Exception in dequeue: Empty
Type (debug) to enter the debugger.

You can run the program at http://ideone.com/uEPCIJ.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: