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.
A solution in Racket.
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: