Queue

Structure and operations

A queue is a linear list for which all insertions are made at one end of the list; all deletions (and accesses) are made from the other end.

With queues we speak of the front and the rear of the queue, also known as head and tail. Items are enqueued to the rear of the queue, and are dequeued from the front position.

Queues feature the so called first-in-first-out "FIFO" behaviour. This is demonstrated by the following snapshot.

@Test
public void testQueue() {
    Queue queue = factory.newQueue();
    Assert.assertTrue(queue.isEmpty);

    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    Assert.assertEquals(1, queue.dequeue());
    Assert.assertEquals(2, queue.dequeue());
    Assert.assertEquals(3, queue.dequeue())
    Assert.assertTrue(queue.isEmpty)
}

Bounded and unbounded queues

Queues come in two varieties: bounded and unbounded. Bounded queues have limited capacity (an int), unbounded have no upper limit.

@Test
public void testBoundedQueue() {
    Queue queue = factory.newQueue(10);
    Assert.assertTrue(queue.isEmpty);

    for (int i = 0; i < 10; i++) {
        queue.enqueue(i);
    }
    Assert.assertTrue(queue.isFull());
}

Queue underflow and overflow

Attempting to dequeue from empty queue results in underflow. Attempting to enqueue to full queue (bounded variety) results in queue overflow.

@Test (expected = UnderflowException.class)
public void testQueueUnderflow1() {
    Queue queue1 = factory.newQueue();
    Assert.assertTrue(queue1.isEmpty);

    queue1.dequeue();
}

@Test (expected = UnderflowException.class)
public void testQueueUnderflow2() {
    Queue queue2 = factory.newQueue(10);
    Assert.assertTrue(queue2.isEmpty);

    queue2.dequeue();
}

@Test (expected = OverflowException.class)
public void testQueueOverflow() {
    Queue queue3 = factory.newQueue(10);
    Assert.assertTrue(queue3.isEmpty());

    for (int i = 0; i < 10; i++) {
        queue3.enqueue(i);
    }
    Assert.assertTrue(queue3.isFull());

    queue3.enqueue(10);
}