A warm Hello to all the readers!
In this post, we will understand another data structure i.e. Queue.
See the image. It shows a queue of men standing waiting for their turn.
Queue is basically a double sided stack. On one side, elements are inserted and on the another side, the elements are removed.
A queue data structure is also known as First in First Out structure. In short it is termed as FIFO. In FIFO, the element that is inserted first is removed first unlike stack. The first man entering the queue will also be the first to leave the queue.
What are Queue Operations?
In a queue there are two operations that can be performed. Enqueuing and Dequeuing of elements in the queue.
Enqueuing an element means inserting it in the back of queue. And dequeuing an element means removing it from the front of queue.
When queue if full and no more element can be inserted, then enqueuing results in overflow. And when queue is empty and no element can be removed, then dequeuing results in underflow.
What is the Time Complexity of Queue Operations?
- Inserting an element – O(1) since element is inserted in the rear of queue
- Removing an element – O(1) since element is removed from the front of queue
- Searching an element – O(n) since entire queue has to be traversed to find the matching element
- Accessing an element – O(n) Again queue has to be traversed to access it. There is no indexing like array.
What are the Real World Practical Examples of Queue?
Some real world applications of queue data structure are:
- Printer
- Application responding to requests in the order they come in
- Scheduling a job by CPU
- People standing in a line for buying tickets
What is a Priority Queue?
A priority queue is a variant of queue data structure. In this the elements are sorted in ascending order before storing in the queue. Rest of the operations are same as that of queue and with the same time complexity.
