This abstract data structure follows the First In First Out(FIFO) concept where the data stored first is accessed first. We can implement queues using Structures, Arrays, Linked-lists or Pointers. Queue uses 2 data pointers – head and tail for Enqueue and Dequeue operations
Applications:
A ticketing system is a real-world example for the queue where the person first in the line is served first and the one at the end of the line is served last.A queue is a special Data Structure efficiently used for buffering. This concept works similar to the print queue where the jobs buffered are printed based on the order of requests received. We can also use queues to prioritize interrupts to address based on their priority. Another simple example of a queue system is the first-come-first-served calls answered in a call center.
Queue Operations:
The life cycle of a queue involves initializing, adding items to the queue (enqueue), retrieving items from the queue (dequeue) and deleting the queue from memory.Learning Queue is incomplete without understanding the steps involved in Enqueue and Dequeue operations.
Enqueue:
Enqueue operation manipulates only the tail pointer and does not hinder the head pointer. We insert data in a queue with the following steps:
- Check if the queue is empty
- If the queue is not empty, stop the operation
- If the queue is empty, increment the tail pointer to point to the next available space
- Insert the data in the newly created space
- Now that becomes the current tail element of the queue
Algorithm for Enqueue:
|
Enqueue(data)
{
if queue is empty
{
tail = tail +1
queue[tail] = data
}
else
exit
} |
Dequeue:
Dequeue operation does not manipulate the tail pointer. Here, data is removed from the Queue with the following steps:
- Check if the queue is empty
- If the queue is not empty, stop the operation
- If the queue is not empty, move to the head of the queue
- Remove the data and increment the head pointer to the next position
- Now that becomes the current head element of the queue
Algorithm for Dequeue:
|
Dequeue( ){
if queue is empty
exit
else{
head = head +1
queue[head] = data
}
} |
Types of Queues:
-
A simple queue is a linear queue. We insert data until the queue becomes full.
-
Circular queue, commonly referred to as Ring buffer, is a linear queue where the head of the queue is connected back to the tail. Data is enqueued in the head and dequeued from the tail
Get one step closer to your dream job!
Prepare for your programming interview with Data Structures & Algorithms Interview Questions You’ll Most Likely Be Asked. This book has a whopping 200 technical interview questions on lists, queues, stacks, and algorithms and 77 behavioral interview questions crafted by industry experts and interviewers from various interview panels.