A queue is a linear data structure, similar to the Stack data structure. However, unlike a stack, a queue follows the First-In-First-Out (FIFO) principle. This means that the first item to be added to the queue is the first item to be removed, and the last item added is the last item to be removed. Queues are commonly used in computer science for tasks such as task scheduling, data processing, and communication between processes.
Basics of a Queue
The queue data structure is similar to a real-life queue. For instance, imagine a queue of people waiting to buy tickets at a theme park. The first person in line is the first one to get a ticket, and the last person in line is the last one to get a ticket, following the FIFO principle.
A queue has two basic operations: enqueue and dequeue. Enqueue is the process of adding an item to the end of the queue, while dequeue is the process of removing the item from the front of the queue.
Let's take an example to understand the working of a queue using the theme park analogy:
Initially, the queue is empty.
When the first person arrives, they are added to the queue (enqueued). The first person is also the last in this case.
When the second person arrives, they join the queue behind the first person (enqueued).
This process continues until all people have joined the queue.
When it's time for the tickets to be sold, the first person in line (at the front of the queue) gets their ticket (dequeued).
The next person in line now becomes the first person and they get their ticket (dequeued).
This process continues until all people have gotten their tickets.
In this example, the queue ensures that everyone gets a ticket in the order they arrive, without any confusion or cutting in line.
Array Implementation
The Array object in JavaScript can be used to implement a queue using inbuilt array methods. Arrays have a push() method which allows us to add elements to the end of the array (enqueue) and a shift() method which allows us to remove the first element from the array (dequeue).
For example, let's consider the following code:
let queue = []
queue.push(1) //enqueue 1
queue.push(2) //enqueue 2
queue.push(3) //enqueue 3
console.log(queue) //[1,2,3]
queue.shift() //dequeue 1
queue.shift() //dequeue 2
queue.shift() //dequeue 3
console.log(queue) // []
As you can see, we have implemented a basic queue using an array in Javascript. The array or the queue was initially empty. Then three values, 1, 2, and 3, are enqueued to the queue using the push() method. The console.log statement shows the contents of the queue array which is [1,2,3]. Then, three dequeue operations are performed using the shift() method which removes the values from the front of the queue. The first call to shift() removes 1, the second call removes 2, and the third call removes 3. After these three dequeue operations, the queue array is empty, as seen from the output of the second console.log statement which is [].
Class-based Implementation
In addition to using arrays, queues can also be implemented as classes in JavaScript. A class-based implementation provides a more object-oriented approach and can be used to encapsulate the data and behavior of a queue. This can be especially useful in larger projects where you want to maintain a clear separation between different components.
Here's an example of how you can implement a stack as a class in JavaScript:
class Queue{
constructor(){
this.storage= {};
this.head = 0
this.tail = 0
}
//enqueue
enqueue(element){
this.storage[this.tail] = element
this.tail++
}
//dequeue
dequeue(){
const returnVal = this.storage[this.head]
delete this.storage[this.head]
this.head++
return returnVal
}
}
const ticketLine = new Queue()
ticketLine.enqueue("Alex")
ticketLine.enqueue("Jack")
ticketLine.enqueue("James")
console.log(ticketLine) //{storage: {0:"Alex",1:"Jack",2:"James"}, head: 0, tail: 3}
ticketLine.dequeue()
ticketLine.dequeue()
ticketLine.dequeue()
console.log(ticketLine) //{storage: { }, head: 3, tail: 3}
Use Case
Queues are often utilized in a variety of real-life applications and systems where a first-come-first-serve order needs to be maintained.
For instance, a queue can be used to manage print jobs in a printer where the first job sent will be printed first and the ones sent later will follow suit. In operating systems, queues are used for task scheduling where tasks added first will be executed first and the ones added later will follow. Queues can also be used for resource sharing, such as network connections or CPU time, where when a resource is requested, the request is added to the end of the queue and when the resource becomes available, it is assigned to the request at the front of the queue.
The ability to process data in a specific order makes queues a valuable tool in a wide range of applications.
Conclusion
A queue is a useful data structure for tasks that require items to be processed in the order they are received. In this article, we have discussed the simplest implementation of the queue data structure. There are many ways to extend and refine our implementation. I recommend continuing to explore implementations and adapting them to your need.