A queue or FIFO (first in, first out) is an abstract data type that serves as a collection of elements.

It has following principal operations:

  1. Enqueue - the process of adding an element to the collection.(The element is added from the rear side
  2. Dequeue - the process of removing the first element that was added. (The element is removed from the front side).
  3. Front - Get the front item from queue.
  4. Rear - Get the last item from queue.

A queue is a sequence of elements such that each new element is added (enqueued) to one end, called the back of the queue, and an element is removed (dequeued) from the other end, called the front. Also known as a FIFO (First In First Out) buffer.

There are two ways to implement a queue:

Queue will be useful in following scenarios-

  • When a resource is shared among multiple consumers
    • e.g. Include CPU scheduling, Disk Scheduling, etc.
  • When data is transferred asynchronously between two processes. 
    • e.g. Include IO Buffers, pipes, file IO, etc.

The complexity of Queue:

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Queue

Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)

 

Examples:

  • Applications:
    • CPU Scheduling
    • Disk Scheduling
  • Algorithm;
    • Breadth First Search