What is a Queue?

2K

A queue is a linear data structure that stores data (similar to Linked Lists and Stacks). In a queue, the order in which the data arrives is important.

Definition: A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at other end (front). The first element that you insert, is the first one that is removed. This makes it a First In First Out (FIFO) or Last In Last Out (LILO) list.

Basic Operations:

The basic operations on this data structure are:

• enQueue: When you want to add an element. You add the new element at the REAR and update the REAR. Suppose you call, enQueue(9)on the above example. 9 will be added at the very end, that is after 15.
• deQueue: This operation removes an element from the queue. You remove the element at the FRONT and update the FRONT. Let us say you call deQueue() on the above example, 2 will be returned to you and the FRONT will update to 5
• peek: To look at the top most/FRONT element. Note that this operation will not remove the element. If you use the peek operation on the above example, you will get the result to be 2.
• isFull: Returns true, if the queue memory/size is full and you cannot add more elements.
• isEmpty: True if there are no more elements that can be removed.

Trying to DeQueue an empty queue is called as underflow and trying to EnQueue an element when it is full, is called as overflow. Generally, we treat them as exceptions. As an example, consider this snapshot:

How does it look like?

A line at reservation counter (movies/airports) explains the concept of a queue. When you enter the line you put yourself at the end of the line.

The person who is standing a the FRONT of the line will be first one to buy the ticket. This person then exits from the “FRONT”.

A little later the head/front of the queue will update and the next person in line would become the head. This will keep on happening until we reach the end/REAR of the queue, and everyone has been served. This is an example of a use case where there is need to maintain the order of arrival.

Direct Applications:-

• Operating systems schedule jobs (with equal priorities) in the order of arrival(eg. a print queue).
• It is also helpful in simulation of real-world queues such as lines at a ticket counter.
• Multi-threading and multi-processing.
• Asynchronous data transfer (file I/O, pipes, sockets).
• Waiting times of customers at a call center.
• Determining number of cashiers to have at a supermarket.

Indirect Applications:-

• Auxiliary data structure for algorithms.
• Component of other data structures.

Video Explanation: