Queue implementation is using underlying data structures (linked list, array) to implement enqueue and dequeue. A queue is First-In-First-Out (FIFO) data structure. New elements are inserted at rear (enqueue), and existing elements are removed from the front (dequeue). Both enqueue and dequeue operation have O(1) complexity.

queue diagram

In this post, linked list is used to implement queue. Linked list is preferred because it is flexible to add and remove elements.  Array is not recommended because it wastes a lot of space if there are many adds and removes. However array can be efficient to implement circular queue. Deque is a queue that can be enqueue and dequeue at both end. It is implemented in doubly linked list.

Table of Content


You are here

you are here

Part 1 – Queue implementation with linked list
Part 2 – Circular queue implementation with array
Part 3 – Circular queue as circular linked list
Part 4 – Deque as doubly linked list


Enqueue

Using linked list, first we need to define a queue node. This class has variables of data and next. Next we define the queue class. It has three class variables: front, rear and length. The front is a pointer to the first node. The rear is a pointer to the last node. The length is to track the length of the list.

The enqueue operation is to add an element at the rear. If the queue is empty, we points both front and rear to the new node. If it is not empty, we simply add the new node to the rear.

Java

Javascript

Python

Doodle

queue with linked list


Dequeue

The dequeue operation is to remove the first node from the queue. First we check whether the queue is empty. If it is empty, the method should return. In this implementation, we simply move the front pointer to the next node. The “removed” node is still in the list without accessible until the linked list is removed from the memory.

Java

Javascript

Python


Peek

Peek is to return the value of the first node. The same as dequeue, we should check whether the queue is empty. If it is not empty, return the value.

Java

Javascript

Python


Print

Print is to print all elements in the queue. Starting from the front node, a while loop is used to iterate through each node till to the rear in the list.

Java

Javascript

Python


Free download

Download queue implementation using linked list in Java, JavaScript and Python
Data structures and Java collections

What data structures can be used to implement a queue?

A queue is abstract data type (ADT), meaning its underneath data structures and implementations is not visible to outside. In theory, data structures to implement a queue are an arrays, a linked list or stacks. Using an array is not space efficient. A linked list is preferred because it is flexible to add and remove elements.