Let me once again use a picture as didactic item.
What you see there is phenomenon called line. Or queue. It forms when demand for some goods is higher than supply. If given product is limited on the market, this fact automatically makes it more desirable. Anyway, Queue, in opposition to Stack, will work on the elements arranged the way they were added.
First In, First Out
Whatever is the reason for the people to stand in this line, one thing is a fact. The person who came first, will be served first, and one who came last, will be served last. This characteristic is called First In, First Out (FIFO).
Queue definitely has better analogies existing in the real world. Line in front of the store, waiting room in the doctor’s office or elevator. All these are bound together by the way they process elements - first is always served first.
Methods
There are basically two methods which operate on the Stack data structure.
- enqueue(element): put an element on the very-first position in Queue
- dequeue(): remove the first-most element in the Queue
Queue Types
It turns out, that Queue has a lot of applications, that’s why a few Types of this data structure were invented. Let’s briefly go through them.
Simple Queue
In this first and fundamental type, we deal with a Queue in the form presented in the Interactive Widget. It simply puts values to the front-most slot through the rear. To get rid of the element, it dequeues it through a front of the structure.
Simple Queue may be used whenever there is a need to put some elements one after another before it gets processed. Good example here are songs on the compact discs or playlist on Spotify.
Circular Queue
As its name suggests, Circular Queue has its first and last slot connected, so it forms a circle. Elements are inserted at the beginning of the Queue and removal is done via the last slot.
When it comes to Circular Queue usage, it shines when presenting a months in a year for that instance, because after reaching the last element, we always go back to the first one. It may be also useful during video streaming, because since new frames are added to the stream, the old ones are being removed at the same time.
Double-Ended Queue or Deque
This type of Queue lets you insert or remove elements from both ends, rear and front. It is very helpful when you need to implement undo operations list.
Priority Queue
This type of Queue data structure inserts elements together with their priority. When elements are being removed, the ones with higher priority will be deleted first.
Usages
Priority Queue is used in the operating system’s scheduler, so it knows which processes have to be run before others. Computers also use this type of Queue, to handle hardware interruptions.