Queue ADT Implementation

The Queue ADT stores arbitrary objects and insertions and deletions of this ADT follow the first-in-first-out (FIFO) scheme i.e. insertions are at the rear of the queue and removals are from the front of the queue. As in a line or queue at a ticket stand, items are removed from the data structure in the same order that they are added.

Main stack operations:

• void enqueue(object): inserts an element at the end of the queue
• object dequeue(): removes and returns the last inserted element

Auxiliary stack operations:

• object front(): returns the front element without removing it
• integer size(): returns the number of elements stored
• boolean isEmpty(): indicates whether no elements are stored

Applications of Queue

Direct applications

• the waiting list, bureaucracy
• access to shared resources (e.g. printer)
• implementing the cache (evicting first cached element)
• OS multiprogramming

Indirect applications

• auxiliary data structures for algorithms e.g in Breadth-First search queue is to store a list of the nodes that need to be processed.
• component of other data structures

Linked List-based stack

Queue ADT implementation with Linked List is straightforward by maintaining pointers to both first and last element registered to the list.

Here is Java implementation for queue ADT.

import java.util.NoSuchElementException;
public class MyQueue<T> {
    static class QueueNode<T> {
        T data;
        QueueNode next;

        QueueNode(T data) {
            this.data = data;
            this.next = null;
        }

        @Override
        public String toString() {
            return "(" + data + ")";
        }
    }

    private QueueNode<T> first;

    private QueueNode<T> last;

    void enqueue(T data) {
        QueueNode<T> node = new QueueNode<>(data);
        if (last != null) {
            last.next = node;
        }

        last = node;

        if (first == null) {
            first = last;
        }
    }

    T dequeue() {
        if (first == null) throw new NoSuchElementException();
        T data =first.data;

        first = first.next;

        if (first == null) {
            last = null;
        }
        return data;
    }

    T peek() {
        if (first == null) throw new NoSuchElementException();

        return first.data;
    }

    boolean isEmpty() {
        return first == null;
    }
}

Testing

The above implementation can be validated as below:

@Test
public void testMyQueue() {
    MyQueue<Integer> queue = new MyQueue<>();
    queue.enqueue(4);
    queue.enqueue(9);
    queue.enqueue(13);
    queue.enqueue(18);

    assertFalse(queue.isEmpty());

    // peek
    assertEquals(Integer.valueOf(4), queue.peek());
    assertEquals(Integer.valueOf(4), queue.peek());

    // remove
    assertEquals(Integer.valueOf(4), queue.dequeue());
    assertEquals(Integer.valueOf(9), queue.peek());
    assertFalse(queue.isEmpty());
}

Performance

For n be the number of elements in the Queue

• The space used is O(n)
• Each operation runs in time O(1)

All the source code presented above is available on GitHub.