Queue

A queue is an abstract data type representing a collection of values, with elements added and removed according to the first in, first out (FIFO) principle.

Elements may be enqueued (inserted) at the back of the queue, or dequeued (removed) from the front of the queue. The queue may also be peeked (retrieving the element at the front of the queue without removing it).

A queue effectively restricts the interface of a double-ended queue , by limiting insertion and deletion to the tail and head of the sequence, respectively.

Common operations

Singly-linked list implementation

A queue may be implemented by adapting a singly-linked list , which allows for $\mathcal{O}(1)$-time access, insertion, and deletion (at the head of the list):

 1public class LinkedQueue<E> implements QueueADT<E> {
 2    private final SinglyLinkedList<E> list = new SinglyLinkedList<>();
 3
 4    public int size() { return list.size(); }
 5
 6    public boolean isEmpty() {  return list.isEmpty(); }
 7
 8    public E peek() { return list.first(); }
 9
10    public void enqueue(E e) { list.addLast(e); }
11
12    public E dequeue() { return list.removeFirst(); }
13}

Circular array implementation

A queue may be implemented with a circular static array , which allows for deletion of the first element in $\mathcal{O}(1)$-time.

In a circular array, the position of the logical front of the array is tracked. The array “overflows” back to the start, meaning that the actual index of an element stored at the end of the array is $0$.

To find the actual index of a logical position in a circular array:

1. Add the tracked front index to the logical index
2. Take the remainder of division by the array’s capacity

When deleting the front element, the new front is the next logical position in the array:

 1public class StaticArrayQueue<E> implements QueueADT<E> {
 2    private final static int DEFAULT_CAPACITY = 16;
 3
 4    private E[] data;
 5    private int front = 0;
 6    private int size = 0;
 7
 8    public StaticArrayQueue() { this(DEFAULT_CAPACITY); }
 9
10    public StaticArrayQueue(int capacity) { data = (E[]) new Object[capacity]; }
11
12    public int size() { return size; }
13
14    public boolean isEmpty() { return size == 0; }
15
16    public E peek() {
17        if (isEmpty()) return null;
18        return data[front];
19    }
20
21    public void enqueue(E e) throws IllegalStateException {
22        if (size == data.length) throw new IllegalStateException("Queue is full");
23        int avail = (front + size) % data.length;
24        data[avail] = e;
25        size++;
26    }
27
28    public E dequeue() {
29        if (isEmpty()) return null;
30        var result = data[front];
31        data[front] = null;
32        front = (front + 1) % data.length;
33        size--;
34        return result;
35    }
36}