Queue

Written by

Sonal Moga

A queue can be referred to as a pile of items in which an element is inserted from one end and is removed from another end. Queue follows FIFO (First-In-First-Out) principle and is just opposite in this case from Stack.

To understand the FIFO principle we can take an example of people standing in a line waiting to order a cup of coffee at a cafe. The first customer coming in will be the first one to move out. Thus, a queue is used when some activities are to be done on First Come First serve Basis.

The items are inserted at the rear end and are deleted from the front end.

Queue is a data structure useful in time-sharing systems where many jobs are waiting in the queue for processing. These jobs can be like requesting external device as printer etc. All the jobs are given a processing time and are performed one after another.

Just like a stack, queue also has three basic operations:

  • Push inserts an item in the queue
  • Pop deletes an item from the queue
  • View displays the elements of the queue

Types of Queues

  • Ordinary Queue

    , it is the basic type of queue that we have discussed above. The main disadvantage of this type of queue is that even though there is space in the queue after the deletion of the elements at the front end, the queue still returns Queue Overflow.

 

  • Double-ended Queue

    or called Deque is a special type of data structure where insertion and deletion happen either at the front end or rear end. The operations that can be performed on a deque are

    • Insertion of an item at the front end
    • Insertion of an item at the rear end
    • Deletion of an item from the front end
    • Deletion of an item from the rear end
    • Display the contents of the queue
  • Circular Queue

    is the queue implemented in a circle instead of a straight line. It overcomes the problem of indication of Queue overflow even when there was space in it. The circular queue is contiguous at opposite ends; therefore if there is a space, in the beginning, the rear shifts to the beginning after reaching maximum possible index number.

Queue