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.
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
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class QueueNode<T> { protected T data; protected QueueNode<T> next = null; //Constructor, Time O(1), Space O(1) public QueueNode(T value) { this.data = value; } } public class QueueList<T> { private QueueNode<T> front = null; private QueueNode<T> rear = null; private int length = 0; //Add at the rear, Time O(1), Space O(1) public void enqueue(T value) { QueueNode<T> newNode = new QueueNode<T>(value); if (isEmpty()) { front = rear = newNode; } else { rear.next = newNode; rear = newNode; } length++; } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class QueueNode { //Constructor, Time O(1), Space O(1) constructor(value) { this.data = value; this.next = null ; } } class QueueList { //Constructor, Time O(1), Space O(1) constructor() { this.front = null; this.rear = null; this.length = 0; } //Add at the rear, Time O(1), Space O(1) enqueue(value) { var newNode = new QueueNode(value); if (this.isEmpty()) { this.front = this.rear = newNode; } else { this.rear.next = newNode; this.rear = newNode; } this.length++; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class QueueNode: #Constructor, Time O(1), Space O(1) def __init__(self, value): self.data = value self.next = None class QueueList: #Constructor, Time O(1), Space O(1) def __init__(self): self.front = self.rear = None self.length = 0 #Add at the rear, Time O(1), Space O(1) def enqueue(self, value): newNode = QueueNode(value) if self.isEmpty(): self.front = self.rear = newNode else: self.rear.next = newNode self.rear = newNode self.length +=1 #Check empty, Time O(1), Space O(1) def isEmpty(self): return self.front == None |
Doodle
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//Remove from the front, Time O(1), Space O(1) public T dequeue() { if (isEmpty()) { System.out.println("Queue is empty, cannot dequeue"); return null; } T item = front.data; front = front.next; length--; if (front == null) rear = null; return item; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//Remove from the front, Time O(1), Space O(1) dequeue() { if (this.isEmpty()) { console.log("Queue is empty, cannot dequeue"); return null; } var item = this.front; this.front = this.front.next; this.length--; if (this.front == null) { this.rear = null; } return item; } |
Python
|
1 2 3 4 5 6 7 8 9 10 |
#Remove from the front, Time O(1), Space O(1) def dequeue(self): if self.isEmpty(): return item = self.front self.front = self.front.next self.length -= 1 if (self.front == None): self.rear = None return item |
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
|
1 2 3 4 5 6 7 8 |
//Return front value, Time O(1), Space O(1) public T peek() { if (isEmpty()) { System.out.println("Queue is empty, cannot peek"); return null; } return front.data; } |
Javascript
|
1 2 3 4 5 6 7 8 |
//Return front value, Time O(1), Space O(1) peek() { if (this.isEmpty()) { console.log("Queue is empty, cannot peek"); return null; } return this.front.data; } |
Python
|
1 2 3 4 5 6 |
#Return front value, Time O(1), Space O(1) def peek(self) : if self.isEmpty(): print("Queue is empty, cannot peek") return None return self.front.data |
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
|
1 2 3 4 5 6 7 8 9 10 |
//Print all, Time O(n), Space O(1), n is number of items in queue public void print() { QueueNode<T> node = front; System.out.print("Queue: "); while (node != null) { System.out.print(node.data + " "); node = node.next; } System.out.println(); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 |
//Print all, Time O(n), Space O(1), n is number of items in queue print() { var str = "Queue: "; var node = this.front; while (node != null) { str += node.data +" "; node = node.next; } console.log(str); } |
Python
|
1 2 3 4 5 6 7 8 |
#Print all, Time O(n), Space O(1), n is number of items in queue def print(self) : line = ("queue: ") node = self.front while node != None: line += str(node.data) + " " node = node.next print(line) |
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.