Example: Queue

A queue is a list-like structure that provides restricted access to its elements. Queue elements may only be inserted at the back (called an enqueue operation) and removed from the front (called a dequeue operation). Queues operate like standing in line at a movie theater ticket counter. If nobody cheats, then newcomers go to the back of the line. The person at the front of the line is the next to be served. Thus, queues release their elements in order of arrival. In Britain, a line of people is called a “queue”, and getting into line to wait for service is called “queuing up”. Therefore, it enforces first-in–first-out (FIFO) behavior on the list.

Thus, the queue ADT stores a list of data and supports the following operations:

• Enqueue—insert an object onto the rear of the list.
• Dequeue—remove the object at the front of the list.
• Empty—return true if the queue is empty.

Queues are useful for a number of computing tasks. For example, the ready, waiting, and blocked queues used by the CPU scheduler all use a FIFO protocol. Queues are also useful in implementing certain kinds of simulations. For example, the waiting line at a bank or a bakery can be modeled using a queue.

Image From Java, Java, Java: Object-Oriented Problem Solving, 2022E

Java’s Queue Interface

The Queue interface extends the Collection interface and provides an abstraction of a queue data structure. Note that in Java Queue is not a class. It is an interface with several implementations. Most often, a standard FIFO queue is implemented by a LinkedList. This is not surprising because a queue is a special linked list where we add at one end and remove from the other.

In the Queue JavaDocs you can find a detailed description of the Queue<E> interface. Below we summarize the important methods of the interface.

• boolean add(E e). Adds the specified element to the tail of the queue and returns true as long as the element is
  successfully added.
• boolean offer(E e). Same as add(E e).
• E remove(). Removes and returns the element at the head of the queue. The method throws a NoSuchElementException if the queue is empty.
• E poll(). Same as remove(), but returns null if the the queue is empty.
• E peek(). Returns the element at the head of the queue without removing it. Returns null if the queue is empty.
• E element(). Same as peek(), but throws a NoSuchElementException if the the queue is empty.
• boolean addAll(Collection<? extends E> c). Adds all the elements of the specified collection to the queue in the order defined by the collection’s iterator, and returns true if all the elements are successfully added. The method throws a NullPointerException if the specified collection is null.
• int size(). Returns the size of the queue, i.e. the number of elements in the queue.
• boolean isEmpty(). Returns true if and only if the queue is empty (i.e. size() == 0).
• void clear(). Clears the queue.

The very simple code below shows how to create a queue and use its methods.

import java.util.Queue;
import java.util.LinkedList;
public class QueueDemo {
	public static void main(String[] args) {
    	// Create a new queue
    	Queue<Integer> queue = new LinkedList<Integer>();

    	// Add elements to the queue
    	for (int i = 1; i <= 6; i++) {
        	System.out.println("Adding " + i);
        	queue.add(i);
    	}

    	System.out.println("Queue after elements are added: ");
    	System.out.println(queue);
    	System.out.println();

    	System.out.println("Emptying the queue: ");
    	while (!queue.isEmpty()) {
        	System.out.print(queue.remove() + " ");
    	}
    	System.out.println();

    	System.out.println("Queue after emptying: ");
    	System.out.println(queue);
    	System.out.println();


	}
}

Notice that in the program the queue is created as a linked list. The following is the output of the program, which

demonstrates the FIFO nature of a queue.

The elements leave the queue in the same order as they enter the queue.