Circular queue implementation

The trick here is that you need a pointer to the last element in the circular linked list. Inserting items in the linked list can happen replacing the last element or after the last element. Removing items seems efficient only after the last element.

A queue implementation based on circular linked lists would replace the last element and would remove the first element.

A quick demo:

1. last = null;

2. insert a: a->a; last=a;

3. insert b: a->b->a…; last=b;

4. insert c: a->b->c->a…; last=c;

5. remove first: remove a: c->b->c…; last=c

The code below contains the Java implementations (note that some guarding clauses can be added, and a little more OO love can be shown).

public class CircularQueue<Item> implements Iterable<Item>{
    private CircularLinkedList<Item> list = new CircularLinkedList<Item>();

    public void enqueue(Item item){
        list.insertLast(item);
    }

    public Item dequeue(){
        return list.removeFirst();
    }

    public int getSize(){
        return list.getSize();
    }

    @Override
    public Iterator<Item> iterator() {
        return new CircularLinkedListIterator<Item>(list);
    }
}

public class CircularLinkedListIterator<Item> implements Iterator<Item> {

    private CircularLinkedList<Item>.Node last;
    private CircularLinkedList<Item>.Node current;

    public CircularLinkedListIterator(CircularLinkedList<Item> list) {
        last = list.last;
        current = last.next;
    }

    @Override
    public boolean hasNext() {
        return current != null && current != last;
    }

    @Override
    public Item next() {
        if(!hasNext()){
            throw new NoSuchElementException();
        }
        Item result = current.item;
        current = current.next;
        return result;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

public class CircularLinkedList<Item> implements Iterable<Item> {

    private Node last;
    private int size;

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void insertLast(Item item) {
        if (last == null) {
            last = new Node();
            last.item = item;
            last.next = last;
        } else {
            Node newNode = new Node();
            newNode.item = item;
            newNode.next = last.next;
            last.next = newNode;
            last = newNode;
        }
        size++;
    }

    public Item removeFirst() {
        if (last == null) {
            return null;
        } else {
            Item result = last.next.item;
            if (last.next == last) {
                last = null;
            } else {
                last.next = last.next.next;
            }
            size--;
            return result;
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new CircularLinkedListIterator(this);
    }

    public class Node {
        Item item;
        Node next;
    }
}
Advertisements