Ever wonder how messages in a chat stay in the right order, even on different phones? It's like a waiting line! New messages join at the back, and you see them one by one from the front. Queue, make this happen. We'll learn more about them soon!
You are probably wondering why you need to learn queue data structure, the simple answer is versatility. Queue offers a simple yet powerful way to structure data for various applications. Their flexibility allows them to handle tasks, network traffic, or even user interactions efficiently.
What is a Queue in Data Structures?
A Queue is defined as a linear data structure that is open at both ends and the operations are performed in the First In First Out (FIFO) principle.
Imagine it like a line of people waiting to deposit in the bank. The first person who gets in line (the first element added) is the first to be attended to (the first element to be removed).
The end at which insertion takes place is called the REAR/TAIL(the line the customer enters to wait) while the end at which deletion takes place is called the FRONT/HEAD(the path the customer passes to leave).
Visual Representation Of Queue Data Structure
There are two approaches to considering the structure of a queue and both methods depend on the programmer's approach.
So as a programmer, if you consider the left end as the Front then your Rear will be at the right end.
If you consider the left end as Rear then your Front will be at the right end.
Types of Queue
Simple Queue: In a simple queue, insertion occurs at the rear and removal occurs at the front. It strictly follows the FIFO (First in First out) principle.
Circular Queue: A circular queue is an extended version of a linear queue as it follows the First In First Out principle with the exception that it connects the last node of a queue to its first by forming a circular link. This is useful when memory is limited and you only need to access the most recent elements.
Priority Queue: A priority queue is a special type in the data structure where each element is associated with a priority. In this queue, elements with higher priority are dequeued before the elements with lower priority. If two elements carry the same priority, they are served as per their order in the queue.
Dequeue (Double-Ended Queue): This queue allows insertion and deletion from both ends (front and rear). It acts like a queue with two access points, offering more flexibility than a linear queue.
Applications of Queue
-
Task Scheduling:
- Operating Systems: The operating system in your computer relies heavily on queues to manage tasks for the CPU. Processes are added to a queue, and the CPU picks up the first one in line for execution. This ensures fair allocation of processing power among multiple programs running on your computer.
- Printer Spooling: Ever wondered how multiple print jobs don't clash when sent to a printer? Queues come to the rescue! Print jobs are added to a queue, and the printer processes them one by one, ensuring order and preventing collisions.
-
Buffering:
- Real-time Systems: Queues act as buffers between slow and fast devices. For instance, they can be used to temporarily store keystrokes typed on a keyboard until the CPU is ready to process them.
-
Other Applications:
- Message Passing: Queues are a core component in many messaging systems. Messages are placed in a queue, ensuring they are delivered in the order they were sent, even if the recipient is unavailable.
- Multimedia Players: Playlists in music players can be implemented using queues. Songs are added to the queue, and they are played in the order they were added.
Basic Queue Operations
Enqueue(): Process of adding or storing an element to the end of the queue.
dequeue(): Process of removing or accessing an element from the front of the queue.
peek(): Used to get the element at the front of the queue without removing it.
isEmpty(): Checks if the queue is empty.
Size(): Finds the number of elements in the queue.
Implementation of Queues
Queues can be implemented using Two techniques:
- Implementations of Queue Data Structure using Arrays
- Implementations of Queue Data Structure using Linked List
For this article, our focus would be on the implementation of a queue using the array method
Let’s explore each basic operation.
Prerequisites:
- VS-Code: download and install Vs Code from the official website
- Quokka.js Extension Open VS Code and go to Extension tab (usually on the left sidebar). Search for "Quokka.js" and install the extension by Wallby.js
Running JavaScript Code with Quokka
How to Create a New Quokka File
- Open the Command Palette (Ctrl+Shift+P on Windows/Linux, Cmd+Shift+P on macOS).
- Type "Quokka" and select the option "Quokka: New JavaScript File". This will create a new file with the .js extension that's already set up for Quokka.
- Start writing your JavaScript code in this file. As you type, Quokka will automatically evaluate your code and display the output in a dedicated panel at the bottom of the editor.
- No need to save the file or run it manually. Quokka provides real-time feedback.
Now, let's play around with the implementation of a queue!
isEmpty Operation in Queue Data Structure
This operation returns a boolean value that indicates whether the queue is empty or not.
<script>
isEmpty(){
// return true if the queue is empty.
return this.items.length == 0;
}
</script>
Implementation Example of isEmpty Operation
class Queue {
constructor() {
this.items = [];
}
isEmpty() {
// return true if the queue is empty.
return this.items.length == 0;
}
}
const queue = new Queue();
console.log(queue.isEmpty()); //true
Size Operation in queue data structure
Finds the number of elements in the queue.
Implementation Example of size Operation
class Queue {
constructor(size = 10) {
this.items = Array(size).fill(null);
}
//Finds the number of elements in the queue
size() {
return this.items.length;
}
isEmpty() {
if(this.items.length > 0)
return this.items.length == 0;
}
}
const queue = new Queue();
queue; //Queue{ items: Array(10) [null,null,null,null,null,null,null,null,null,null,]}
console.log(queue.size());
//return false because null is a datatype
console.log(queue.isEmpty()); //false
Enqueue Operation in queue data structure
The enqueue() operation adds or stores an element to the end of the queue. Therefore we can say enqueue operation inserts data into the queue. The following algorithm should be taken to enqueue(insert) data into the queue:
- Step 1: Check if the queue is full.
- Step 2: If the queue is full, return overflow error and exit.
- Step 3: If the queue is not full, increment the rear pointer to point to the next space.
- Step 4: Add the data element to the queue location, where the rear is pointing.
- Step 5: return success.
<script>
// enqueue function
enqueue(element){
// adding element to the queue
this.items.push(element);
}
//This function adds an element at the rear of a queue.
//We have used push() method of array to add an element at the end of the queue.
</script>
Implementation Example of Enqueue Operation
class Queue {
constructor() {
this.items = [];
this.rear = 2;
this.front = 3;
}
//add element to the end of the queue
enqueue(element) {
this.items.push(element);
}
}
const queue = new Queue();
queue.enqueue(7);
queue.enqueue(-1);
console.log(queue); //Queue { items:[7, -1], rear:2, front:3}
Dequeue Operation in queue data structure
Dequeue() operation remove or access an element from the front of the queue. The following algorithm should be taken to dequeue(access) data in queue:
- Step 1: Check if the queue is empty.
- Step 2: If the queue is empty, return the underflow error and exit.
- Step 3: If the queue is not empty, access the data where the front is pointing.
- Step 4: Increment the front pointer to point to the next available data element.
- Step 5: The Return success.
// dequeue function
dequeue()
{
// removing element from the queue
// returns underflow when called
// on empty queue
if(this.isEmpty())
return "Underflow";
return this.items.shift();
}
//This function removes an element from the front of a queue.
We have used the shift method of an array to remove an element
from the queue.
Implementation Example of Dequeue Operation
class Queue {
constructor() {
this.items = [7,-1];
this.rear = 0;
this.front = 0;
}
//remove element from the front of the queue
dequeue() {
if (this.items.length == 0) {
return "Underflow error";
} else this.items.shift();
}
}
const queue = new Queue()
queue.dequeue() //dequeue the first element
console.log(queue) //Queue {items:[-1], rear:0, front:0}
Peek Operation in queue data structure
This function returns the front element of the queue without removing it. We simply return the 0th element of an array to get to the front of a queue.
// peek function
peek()
{
// returns the Front element of
// the queue without removing it.
if(this.isEmpty())
return "No elements in Queue";
return this.items[0];
}
//In this function we have used the length property
of an array and if the array length is 0 then the queue is empty.
Implementation Example of Peek Operation
class Queue {
constructor() {
this.items = [7, -1];
this.rear = 0;
this.front = 0;
}
//get element at the front of the queue without removing it
peak() {
if (this.items.length === 0) {
return "No elements in the queue";
} else {
return this.items[0];
}
}
}
const queue = new Queue();
//peak the first element
console.log(queue.peak()); //7
To summarize, queues represent a foundational concept in computer science, operating under the principle of First In First Out (FIFO). They provide a structured approach to managing data, ensuring orderly processing in various applications such as task scheduling, network communication, and real-time systems. Whether implementing a simple queue for basic operations or exploring advanced variations like circular or priority queues, mastering these concepts equips developers with powerful tools for efficient data handling. Embracing queues in JavaScript not only enhances programming proficiency but also facilitates the development of robust and responsive applications. By understanding and leveraging queues effectively, developers can optimize resource allocation and enhance user experiences across diverse software environments.
Top comments (3)
Awesome read
Understanding Queue data structure made easier! I love the step-by-step guide👏, thank you Rola✨
A good read here 👏
Firstly, your introduction got me to want to read more. And then your detailed explanation of the concept of Queue with illustrations and code made it impressive.
Well done, Rola. 🚀