Queues

The Queue ADT

• The Queue ADT stores arbitrary objects
• Insertions and deletions follow the first-in first-out scheme
• Insertions are at the rear of the queue and removals are at the front of the queue
• Main queue operations:
  • enqueue(object): inserts an element at the end of the queue
  • object dequeue(): removes and returns the element at the front of the queue
• Auxiliary queue operations:
  • object front(): returns the element at the front without removing it
  • integer size(): returns the number of elements stored
  • boolean isEmpty(): indicates whether no elements are stored
• Exceptions:
  • Attempting the execution of dequeue or front on an empty queue throws an EmptyQueueException
• Applications: Waiting lines, Multiprogramming

Array-based Queue

• Use an array of size N in a circular fashion
• Two variables keep track of the front and rear
  • f index of the front element
  • r index immediately past the rear element
• Array location r is kept empty

Algorithm size()
  return (N − f + r) mod N

Algorithm isEmpty()
  return (f = r)

Algorithm enqueue(o)
  if size() = N − 1 then
    throw FullQueueException
  else
    Q[r] ← o
    r ← (r + 1) mod N

Algorithm dequeue()
  if isEmpty() then
    throw EmptyQueueException
  else
    o ← Q[f]
    f ← (f + 1) mod N
    return o

Growable Array-based Queue

• In a enqueue operation, when the array is full, instead of throwing an exception, we can replace the array with a larger one
• Similar to what we did for an array-based stack
• The enqueue operation has amortized running time
  • O(n) with the incremental strategy
  • O(1) with the doubling strategy

Code

• No corresponding built-in Java class

package examples;

public class MyQueue<E> implements Queue<E> {

    private E[] stor = (E[]) new Object[1];
    private int len,head,tail;

    private void expand(){
        E[] newStor = (E[]) new Object[stor.length*2];
        for (int i=0;i<len;i++) {
            newStor[i]=stor[head++];
            if (head==stor.length) head=0;
        }
        stor = newStor;
        head=0;
        tail=len;
    }

    @Override
    public void enqueue(E o) {
        if (len == stor.length) expand();
        stor[tail++] = o;
        if (tail==stor.length) tail=0;
        len++;
    }

    @Override
    public E dequeue() {
        if (len==0) throw new RuntimeException("empty Queue!");
        E ret = stor[head++];
        if (head == stor.length) head=0; // wrap around !
        len--;
        return ret;
    }

    @Override
    public E head() {
        return stor[head];
    }

    @Override
    public int size() {
        return len;
    }

    @Override
    public boolean isEmpty() {
        return len == 0;
    }

    public static void main(String[] args) {
        MyQueue<String> q = new MyQueue<>();
        q.enqueue("a");
        q.enqueue("b");
        q.enqueue("c");
        System.out.println(q.dequeue());        
        System.out.println(q.dequeue());        
        q.enqueue("d");
        System.out.println(q.dequeue());        
        System.out.println(q.dequeue());
    }

}