Queues

The Basics

A queue is a FIFO sequence. Addition takes place only at the tail, and removal takes place only at the head.

Operations

• enqueue(x): add an item at the tail
• dequeue: remove the item at the head
• peek: return the item at the head (without removing it)
• size: return the number of items in the queue
• isEmpty: return whether the queue has no items

Examples

• Line of cars at a light
• Line of people at a deli or bank
• Printer buffer
• Packets waiting at a router
• Simulation
• Many more examples

Representations

• Wrapper around a built-in list object
• Array-based, bounded or expandable (All operations in Θ(1))

  

• Linked (All operations in Θ(1))

  

Queues in Java

There's already a Queue interface in the Java Core API and a whole bunch of implementing subclasses, but we're going to write some queues from scratch because:

• This is the only way for you to really learn how queues work
• You need coding practice, especially with linked structures
• You need to know how to code things up when you find yourself in a very restrictive environment that doesn't have a collections library.

First, an interface

package edu.lmu.cs.rtoal.collections;

/**
 * A small queue interface.  You can query the size of the queue and
 * ask whether it is empty, add and remove items, and peek at the front
 * item.
 */
public interface Queue {

    /**
     * Adds the given item to the rear of the queue.
     */
    void enqueue(Object item);

    /**
     * Removes the front item from the queue and returns it.
     * @exception java.util.NoSuchElementException if the queue is empty.
     */
    Object dequeue();

    /**
     * Returns the front item from the queue without popping it.
     * @exception java.util.NoSuchElementException if the queue is empty.
     */
    Object peek();

    /**
     * Returns the number of items currently in the queue.
     */
    int size();

    /**
     * Returns whether the queue is empty or not.
     */
    boolean isEmpty();
}

The Trivial Wrapper Implementation

package edu.lmu.cs.rtoal.collections;

import java.util.LinkedList;

/**
 * A trivial implementation of the simple queue interface, built as
 * a wrapper around the LinkedList class from java.util.
 */
public class SimpleQueue implements Queue {
    private LinkedList<Object> data = new LinkedList<Object>();
    public void enqueue(Object item) {data.addLast(item);}
    public Object dequeue() {return data.removeFirst();}
    public Object peek() {return data.getFirst();}
    public int size() {return data.size();}
    public boolean isEmpty() {return data.isEmpty();}
}

This is a common design pattern and all developers are expected to know how to do this. Terminology associated with this technique:

• "The queue wraps the list"
• "The list is being adapted to use in a queue context"
• "The queue delegates to the list"
• "The list interface is being narrowed to that of a queue"

A Bounded Array Implementation

Things to note here:

• The capacity is set at creation time
• Adds have a precondition that the queue isn't already full
• Adding to a full queue is a state exception, not an argument exception
• The array itself is effectively circular
• When removing, we take care to nullify the newly unused slot in the array to prevent a possible memory leak

package edu.lmu.cs.rtoal.collections;

import java.util.NoSuchElementException;

/**
 * An implementation of a queue using a fixed, non-expandable array whose
 * capacity is set in its constructor.
 */
public class BoundedQueue implements Queue {
    private Object[] array;
    private int size = 0;
    private int head = 0; // index of the current front item, if one exists
    private int tail = 0; // index of next item to be added

    public BoundedQueue(int capacity) {
        array = new Object[capacity];
    }

    public void enqueue(Object item) {
        if (size == array.length) {
            throw new IllegalStateException("Cannot add to full queue");
        }
        array[tail] = item;
        tail = (tail + 1) % array.length;
        size++;
    }

    public Object dequeue() {
        if (size == 0) {
            throw new NoSuchElementException("Cannot remove from empty queue");
        }
        Object item = array[head];
        array[head] = null;
        head = (head + 1) % array.length;
        size--;
        return item;
    }

    public Object peek() {
        if (size == 0) {
            throw new NoSuchElementException("Cannot peek into empty queue");
        }
        return array[size - 1];
    }

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

    public int size() {
        return size;
    }
}

    Queue q = new BoundedQueue(4);
    q.enqueue("A");
    q.enqueue("B");
    q.enqueue("C");
    q.dequeue();
    q.enqueue("D");
    q.dequeue();
    q.enqueue("E");
    q.enqueue("F");

A Linked Implementation

This particular version uses dual head and tail pointers. Note here:

• Adding to an empty queue is a little different than adding to a queue that already has elements, because we have to update the head in the former case but not the latter.
• Removal has three distinct cases: removing from a queue with more than one element, removing the last element, and removing from an empty queue.

package edu.lmu.cs.rtoal.collections;

import java.util.NoSuchElementException;

/**
 * An implementation of a queue using singly linked nodes.  The
 * queue itself maintains links to both the head and the tail
 * node, so that both enqueuing and dequeueing are O(1).
 */
public class LinkedQueue implements Queue {
    private class Node {
        public Object data;
        public Node next;
        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node head = null;
    private Node tail = null;

    public void enqueue(Object item) {
        Node newNode = new Node(item, null);
        if (isEmpty()) {head = newNode;} else {tail.next = newNode;}
        tail = newNode;
    }

    public Object dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Object item = head.data;
        if (tail == head) {
            tail = null;
        }
        head = head.next;
        return item;
    }

    public Object peek() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        return head.data;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public int size() {
        int count = 0;
        for (Node node = head; node != null; node = node.next) {
            count++;
        }
        return count;
    }
}

Class Diagram

Unit Testing

Here is what we need to test:

• A queue is empty on construction
• A queue has size 0 on construction
• After n enqueues to an empty queue, n > 0, the queue is not empty and its size is n
• If one enqueues x then dequeues, the value dequeued is x.
• If one enqueues x then peeks, the value returned is x, but the size stays the same
• If the size is n, then after n dequeues, the stack is empty and has a size 0
• If one enqueues the values 1 through 50, in order, into an empty queue, then if 50 dequeues are done the values dequeues are 1 through 50.
• Dequeueing from an empty queue does throw a NoSuchElementException
• Peeking into an empty queue does throw a NoSuchElementException
• For bounded queues only, pushing onto a full stack does throw an IllegalStateException

We really have three classes to test, but the test cases share a bunch of things in common; the common tests can go in a base class.

package edu.lmu.cs.rtoal.collections;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

import java.util.NoSuchElementException;

import org.junit.Test;

/**
 * Base test for any class that implements the Queue interface.
 */
public abstract class QueueTest {

    /**
     * The queue to use in all the tests: set this in subclasses.
     */
    protected Queue q;

    @Test
    public void testNewQueueIsEmpty() {
        assertTrue(q.isEmpty());
        assertEquals(q.size(), 0);
    }

    @Test
    public void testInsertsToEmptyQueue() {
        int numberOfInserts = 6;
        for (int i = 0; i < numberOfInserts; i++) {
            q.enqueue("zzz");
        }
        assertTrue(!q.isEmpty());
        assertEquals(q.size(), numberOfInserts);
    }

    @Test
    public void testEnqueueThenDequeue() {
        String message = "hello";
        q.enqueue(message);
        assertEquals(q.dequeue(), message);
    }

    @Test
    public void testEnqueueThenPeek() {
        String message = "hello";
        q.enqueue(message);
        int size = q.size();
        assertEquals(q.peek(), message);
        assertEquals(q.size(), size);
    }

    @Test
    public void testFiftyInThenFiftyOut() {
        for (int i = 0; i < 50; i++) {
            q.enqueue(i);
        }
        for (int i = 0; i < 50; i++) {
            assertEquals(((Integer)q.dequeue()).intValue(), i);
        }
    }

    @Test
    public void testRemovingDownToEmpty() {
        int numberOfRemoves = (int)(Math.random() * 20 + 1);
        for (int i = 0; i < numberOfRemoves; i++) {
            q.enqueue("zzz");
        }
        for (int i = 0; i < numberOfRemoves; i++) {
            q.dequeue();
        }
        assertTrue(q.isEmpty());
        assertEquals(q.size(), 0);
    }

    @Test(expected=NoSuchElementException.class)
    public void testRemoveOnEmptyQueue() {
        assertTrue(q.isEmpty());
        q.dequeue();
    }

    @Test(expected=NoSuchElementException.class)
    public void testPeekIntoEmptyQueue() {
        assertTrue(q.isEmpty());
        q.dequeue();
    }
}

package edu.lmu.cs.rtoal.collections;

import org.junit.Before;
import org.junit.Test;

/**
 * Unit test for SimpleQueue.
 */
public class SimpleQueueTest extends QueueTest {

    @Before
    public void makeSimpleQueue() {
        q = new SimpleQueue();
    }

    @Test public void stupidPieceOfCrapMethodForEclipse() {}
}

package edu.lmu.cs.rtoal.collections;

import org.junit.Before;
import org.junit.Test;

/**
 * Unit test for LinkedQueue.
 */
public class LinkedQueueTest extends QueueTest {

    @Before
    public void makeLinkedQueue() {
        q = new LinkedQueue();
    }

    @Test public void stupidPieceOfCrapMethodForEclipse() {}
}

package edu.lmu.cs.rtoal.collections;

import org.junit.Before;
import org.junit.Test;

/**
 * Unit test for BoundedQueue.
 */
public class BoundedQueueTest extends QueueTest {
    private static int CAPACITY = 60;

    @Before
    public void makeBoundedQueue() {
        q = new BoundedQueue(CAPACITY);
    }

    @Test(expected=IllegalStateException.class)
    public void testEnqueueToFullQueue() {
        for (int i = 0; i < CAPACITY; i++) {
            q.enqueue("abc");
        }
        q.enqueue("abc");
    }
}