Introduction – Concept of Queue in Data Structure
Queue in data structure is kind of a list in which collections of elements have a linear data structure where items get inserted from one end and deleted from another end. Insertion end is considered as rear and deletion end is considered as front end of queue. The principle of queue is a “FIFO” or “First-in-first-out”. Concept of a queue is very important type of data structure in programming.
You can corelate the concept of Queue in data structure as a vehicle is in queue at toll plaza, so that each vehicle gets scanned by fast tag scanner. In that, the car which come first will get scanned and exit first.
Like a stack, a queue is also an abstract data type. With queue, the first item added to the queue is the first item to be removed. That’s why the acronym “FIFO” is used in queues: First In, First Out. As with a line of people, a queue is usually depicted horizontally. It’s also common to refer to the beginning of the queue as its front, and the end of the queue as its back.
Characteristics of Queue:
- Queue can handle multiple data.
- We can access both ends.
- They are fast and flexible.
Queue Representation:
Like stacks, best way to represent queue is linear array. Queue is implemented using the array and variables used during the implementation are:
- Queue: the name of the array storing queue elements.
- Front: the index where the first element is stored in the array representing the queue.
- Rear: the index where the last element is stored in an array representing the queue.
Basic Operations performed in Queue
-
Enqueue
-
Dequeue
Enqueue:
Inserting data into queue data structure is Enqueue. To perform enqueue operation, following steps were followed:
🪜1️⃣First, check status of Queue.
🪜2️⃣If the Queue is full then display the Queue overflow message and exit.
🪜3️⃣If it is not full, REAR pointer will be incremented to point to the next empty space.
🪜4️⃣Add the data where the REAR is pointing.
🪜5️⃣Return to success.
🧑💻Algorithm for Enqueue Implementation
👉procedure enqueue(data)
if queue is full
return overflow
end if
rear <- rear+1
queue[rear]<- data
return true
end procedure👈
Dequeue
Removal or exit out data from queue is Dequeue. To remove data from queue, following steps need to be follow:
🪜1️⃣Check status of Queue.
🪜2️⃣If the Queue is empty then display the Queue underflow message.
🪜3️⃣If the Queue is not empty, then find the data where FRONT is pointed.
🪜4️⃣Now increase the FRONT pointer to point to the available data.
🪜5️⃣Now return to success.
🧑💻Algorithm for Dequeue implementation:
👉procedure dequeue
if queue is empty
return underflow
endif
data = queue[front]
front <- front+1
return true
end procedure👈
Real-world applications of a queue:
✅CPU task scheduling.
✅Queues are used in trees traversals like the “Level Order” traversal of trees.
✅Serving requests on a single shared resource, like a printer, CPU task scheduling, etc.
✅In real life scenario, Call Center phone systems use Queues to hold people calling them in order, until a service representative is free.
✅Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e First come first served.
✅A real-world example of the queue can be a single-lane one-way road, where the vehicle enters first, exits first. More real-world examples can be seen as queues at the ticket windows and bus stops.
Types of Queues in Data Structure
There are four different types of queues in data structures:
▶️Simple Queue
▶️Circular Queue
▶️Priority Queue
▶️Double-Ended Queue (Deque)
For detailed study you can Buy Books on Data Structure & Algorithms
