Queue Data Structure: FIFO, Head and Tail, Enqueue, Dequeue

In this tutorial, you will learn about the abstract data type “queue”:

• How does a queue work?
• What are its operations called – and what are they called in Java?
• Which variants of the queue are there?
• What are the applications for queues?
• How expensive are the enqueue and dequeue operations?

What Is a Queue?

A queue is a sequence of elements where the elements are inserted on one side and taken out in the same order on the other side.

You can think of it as a queue at a checkout or a government office:

Arriving customers queue up at the end of the line (right in the picture). Once a customer has been served, the next one from the head of the queue (left) takes their turn.

Therefore, the person who has queued first also gets the first turn. That is why we speak of the first-in-first-out (FIFO) principle.

FIFO Principle for Queues

With the abstract data type “queue”, this can look like the following example:

The graphic shows a queue containing the elements 6, 7, 8, etc., to 13. The 5 has just been taken from the front of the queue (also called “head”, on the left of the picture), and the 14 is just being inserted at the back of the queue (also called “tail” or “rear”, on the right of the picture).

Queue Operations: Enqueue and Dequeue

We refer to the queue’s operations as follows:

• “Enqueue”: Inserting new elements at the back of the queue
• “Dequeue”: Removing elements from the head of the queue
• “Peek” or “Front”: Viewing the element at the head without removing it (optional)

The dequeue operation cannot remove anything from an empty queue. If a queue has a fixed capacity and is full, the enqueue operation cannot insert anything. Each implementation decides for itself how it reacts – with a special return value or with an exception.

The Queue Operations in Java

The JDK’s Queue interface offers each of the three operations in two variants: one throws an exception if the operation is not possible; the other returns a special value.

Operation	In case of error: exception	In case of error: return value
Enqueue	add()	offer() – false if the queue is full
Dequeue	remove()	poll() – null if the queue is empty
Peek	element()	peek() – null if the queue is empty

add() throws an IllegalStateException; remove() and element() throw a NoSuchElementException. By the way, most queue implementations have no capacity limit – for them, inserting never fails.

Variants of the Queue

In this tutorial series, you will get to know three variations of the simple FIFO queue:

• Priority queue: It does not remove the elements in the order in which they were inserted, but according to their priority. It thus deviates from the FIFO principle. The JDK provides the class PriorityQueue, among others, for this purpose.
• Deque (“double-ended queue”): It allows inserting and removing at both ends. You can learn more about it in the tutorial series on deques.
• Bounded and blocking queues: A bounded queue has a fixed capacity. A blocking queue makes the calling thread wait until an element is available (when removing) or until space is free (when inserting). I explain both in the article about the BlockingQueue interface.

Applications for Queues

One application area of queues we all know is the printer queue. Various programs place print jobs there, and usually, there is only one printer, which then processes the jobs one after the other.

A technical application example is the processing of HTTP requests in a web server. A web server usually works with a thread pool for processing requests simultaneously. If more requests come in than can be processed at the same time, the thread pool is at capacity. Additional requests are then queued and processed in first-in-first-out order as soon as more threads are available.

Algorithms use queues, too. In the level-order traversal of a binary tree, a breadth-first search, the algorithm keeps the nodes still to be visited in a queue – that way, it visits the nodes level by level.

Time Complexity of Queue Operations

You can find an introduction to time complexity in the article “Big O Notation and Time Complexity – Easily Explained”.

Queues are usually implemented with arrays or linked lists. In both variants, the effort for the enqueue and dequeue operations is constant, i.e., it does not change with the length of the queue.

Therefore, the time complexity of these operations is O(1).

There is one exception with the array: if it is full and the queue is to keep growing, the enqueue operation must create a new, larger array and copy all elements into it – this one call costs O(n). Because the array grows in proportion to its size each time (to 1.5 to 2 times its size in this series’ ArrayQueue), this rarely happens, and averaged over many calls, the effort remains constant. This is called amortized O(1).

For practice purposes, you can also implement a queue with stacks (more on this in a later part of the tutorial). With the variant shown there, however, the enqueue operation costs O(n): for each new element, all existing elements are shifted twice.

Outlook

In the next part of the tutorial, you will get to know Java’s Queue interface in detail: its methods, the class hierarchy, and which of the JDK implementations to use when.