A queue is an awesome data structure that works primarily on the First In First Out policy. But there is never a one size fits all solution. Sometimes, you may encounter situations when a standard queue is not enough. Fortunately, there are different models available which work on the same underlying idea. These different queue types are:
- Standard
- Circular
- Priority
- Double-ended (Deque)
Let us learn about each of them one by one.
Standard Queue:
This is the most basic version which follows the First In First Out (FIFO) principle. New elements are added at the rear and removed from the front. It is really essential in job scheduling scenarios like queuing up jobs for a printer, keeping a record of which task comes first for processing and so on. Nothing very special about it.
Circular Queue:
A circular queue has a basic structure as a standard queue but with a slight twist.
A CPU or a computer processor can only do one task at a time, but when you are using your computer, it may feel that you are doing several tasks at once. How is this made possible? Internally, what happens is that the CPU will give a fraction of its processing power to each of the task. This keeps on happening in a cyclic order, and it occurs so fast that we get an illusion as if the tasks are running simultaneously.
This is achieved by making a circular queue. We assign the next of REAR to the FRONT of the queue. Each element in the queue is a task that the CPU has to perform. Upon reaching the last task, the CPU starts processing the first task again, and hence all the tasks are running.
Priority Queue:
Out of all the queue types, a priority is one which is extremely important. The idea behind this queue is that not all tasks have the same priority of execution. For example, a task said by your boss/senior has a higher priority over your personal task. The basic structure looks something like this:
Let us suppose you are writing a code for a mobile phone. It might have several tasks like attending a call, playing a game, using an app, updating software etc. You cannot put everything in just one queue. Think what would happen. If you are playing a game, and a call rings, it gets added to the task queue. Based on the FIFO policy, it would not be processed, until you exit the game. This will be an example of a bad design.
What we do to solve this issue is create different queues and assign priorities to them. Tasks like attending a call would have the highest priority. If you are playing a game now and a call rings, the game would stop and the CPU would process the call first.
Similarly, there can be a queue to complete all your passive tasks like updating the phone or running a virus scan. They can occur when your queue of games/apps is empty, or your phone is idle.
You can definitely create more priorities as per your requirement but the basic idea will still remain the same. The elements in the highest priority queue are consumed first.
Double-ended Queue (Deque):
In a standard queue, you can only add at the REAR and remove elements at the FRONT. A deque is one of the special queue types where you can add and remove elements at both the ends.
This kind of queue is helpful in certain applications like your browser back and forward buttons. You can navigate to any page in your history both forward and backwards. Even if you decide to open up a new webpage, you can add it to the end of the queue.
Video Explanation:
