The Queue data structure implementation is studied in most Computer Science courses on Data Structure and Algorithms. In this post, you will learn one implementation of this important data structure.
One of my favourite books to study data structure is Introduction to Algorithms by Cormen.
Table of Contents
- What is a Queue
- Queue operations
- Queue data structure implementation using linked lists
- Example of usage of the Queue data structure
- Summary
What is a Queue
A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the first object going into the queue is the first one going out of the queue.
The Operations you should implement in queue data structure are only four, because of the FIFO principle. So, you should enforce the FIFO principle in a queue data structure implementation through the operations.
Queue operations
A queue data structure has only 4 operations. Some programming languages have implementations with more operations. However, if you use them, you probably are violating the FIFO principle.
The operations are the following:
- enqueue: add an element to the queue. There is no need to specify the position of the new element. Because it will go to the end of the queue.
- dequeue: removes an element from the queue. There is no need to specify what element you want to remove. I will always be the first element.
- front: this operation will return the first element in the queue.
- isEmpty: returns true if the queue is empty, otherwise, it returns false.
You need only the operations above to use the Queue data structure to solve problems. Extra operations like size, usually don’t make sense in this data structure.
To implement the Queue data structure, we can use arrays or linked lists.
I won’t show here the implementation with arrays because it has a fixed number of elements.
Queue data structure implementation using linked lists
When you study data structures, the first data structure you implement is the list data structure.
You implement a list using arrays or linked lists.
Here, we are going to use the Java linked list to implement the queue data structure.
public class Queue <T> {
private LinkedList<T> info;
Queue(){
info = new LinkedList<>();
}
public void enqueue(T elem){
info.add(elem);
}
public T dequeue(){
return info.removeFirst();
}
public T front(){
return info.getFirst();
}
public boolean isEmpty(){
return info.isEmpty();
}
}
In this case, we are reusing the operations implemented in a linked list. Doing that, we are following one of the principles of Object-Oriented Programming: reusability. You can read more about OOP principles in this post.
You can use the Queue data structure to solve computational problems. The way to do it, is by using only the four methods implemented above. Let’s see an example.
Example of usage of the Queue data structure
The usual way to use the Queue data structure is by using a while loop and the operation isEmpty.
Search operations are not common in a queue. But, you can implement them using an auxiliary queue as in the console application example below.
class QueueUsageExample{
public static void main(String[] args) {
Queue<Integer> queue = new Queue<>();
queue.enqueue(1);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
//Print all the elements in the queue and
//the queue must keep its initial state
Queue<Integer> aux = new Queue<>();
Integer elem;
while (!queue.isEmpty()){
elem = queue.dequeue();
System.out.println(elem);
// Add the element to an auxiliary queue
aux.enqueue(elem);
}
// Put back the elements into the original queue
// using the auxiliary queue
while (!aux.isEmpty()){
queue.enqueue(aux.dequeue());
}
}
}
You can see another example of the Queue data structure usage in this post.
Summary
You can use the Queue data structure to model situations that follow the FIFO principle.
To solve problems using queues you only need four operations: enqueue, dequeue, front and isEmpty.
H@ppy coding!
Related posts:
