Queue Data Structure

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

• How does a queue work?
• What are the applications for queues?
• Which queue interfaces and classes are available in the JDK?
• What are blocking, non-blocking, bounded, and unbounded queues?
• How to implement a queue in Java?

What Is a Queue?

A queue is a list 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 checkout or a government office:

Arriving customers queue up at the end of the line (right in the picture). Once a customer has been processed, the next customer 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 was just 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)

(By the way, the corresponding methods of the Java queue implementations are called differently; more about this in the next part of the tutorial, “Java Queue 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.

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 overhead for the enqueue and dequeue operations is constant, i.e., the overhead does not change with the length of the queue.

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

For practice purposes, you can also implement a queue with stacks (more on this in a later part of the tutorial). However, the time complexity is then higher.