Queue
In our last Episode 6 (https://www.garudax.id/pulse/stack-osman-mohammed/?trackingId=ROFURiQNtH0pj%2FdPZXSkvg%3D%3D) we learned about stack data structure. In this episode, we are going to learn about the below things on the Queue data structure.
1) What is a Queue?
2) Architecture and Characteristics?
3 ) Operations and their Run Time Complexity?
4) Run Time Complexity Summary?
So let's get started.
1) What is a Queue?
The Queue is a linear data structure that follows a certain way to perform operations on data.
What is this certain way called?
- First In First Out (FIFO)
- or
- Last In Last Out (LILO)
Unlike Stack which follows LIFO, Queue follows FIFO.
2) Architecture and Characteristics?
We have different types of Queues like Simple and Priority. For this article I will just talk about the simple queue, later I will append the article with another type called priority.
The reason we call Queue Data Structure as Queue because it behaves exactly like a real-world Queue of Persons where people join from the back and leave from the front after getting their need addressed. In the below pic, you can see people are waiting in a queue to be checked out by the cashier.
The main idea behind the Queue concept is when you have a resource (this can be person, machine, or anything ) that needs to be shared among many entities(this can be again person, machine, or anything) or When you have a resource which needs to process service requests of many entities at a single point in time we tend to form a queue. I still remember, in my childhood days, we had only one bicycle among 3 siblings, we use to take turns and ride it. This was my real-life example of a Queue data structure, there must be yours as well, please think about it.
3 ) Operations and their Run Time Complexity?
We have 5 basic operations in the Queue Data Structure.
- Enqueue
- Dequeue
- Peek
- isEmpty
- isFull
Enqueue Operation
When data is added to the queue from the back is called Enqueue operation. In this case, the data is waiting in the queue to get processed by Resource. Time complexity is O(1).
Dequeue Operation
When data is removed from the front of the queue is called dequeue operation. In this case, the data is processed by Resource, and data is deleted from the queue. Time complexity is O(1).
Peek Operation
When data is removed from the front of the queue without deleting it is called Peek operation. This is equivalent to how cashier while checking out products peek to check who's next in the line. Time complexity is O(1).
Is Empty and Is Full Operations
These two Empty and Full operations are performed to check whether the queue is empty and full respectively. Time Complexity is O(1).
4) Run Time Complexity Summary?
I would like to conclude the episode 7 of our Season 1 here, stay tuned for the episode 8.
References
- Data Structures and Algorithms Made Easy in Java - Narasimha Karumanchi
- https://www.bigocheatsheet.com/
- https://www.dreamstime.com/
Disclaimer
This article is governed by the "Fair Use" doctrine and is only for the purpose such as criticism, comment & teaching.
Note:- This is a living article.