What is Queue Data Structure ?


What is Queue ?

To better understand the concept of queue , let's start with an analogy .
You may have seen a line of peoples waiting for reservation at a railway reservation counter  . A new person who comes , takes his or her place at the end of line and a person at the front of line  get his reservation first and leaves the queue .

Queue is a linear data structure . 
The concept of queue data structure is exactly the same as above analogy .
The unique feature of queue is that the insertion take place at one end (usually Rear end) and deletion take place at other end(usually Front end ) . 
 In the queue , the elements are processed in the order of arrival . In other words we can say that Queue is first come first serve . 
The element inserted first will be deleted first . Therefore  Queue is called as First In First Out (FIFO) .

Another examples of queue includes , line of people waiting for bus at bus stop , queue of jobs waiting for execution on computer . 

Queue as an Abstract Data Type (ADT)
Queue is the linear collection of items that can be deleted from one end known as Front and can be inserted from in e end known as Rear of the queue . 

 Queue Data Structure has following finite set of elements to define the Queue .

 Data elements : Collection of same type of data elements in a queue . 
Front : A variable used to hold the index of starting position of queue . 
Rear :  A variable used to hold the index position of end /last data element .

 Operations 
Queue is an ADT with these operations 

IsEmpty() :  IsEmpty() is used to verify that queue is empty or not . 
It returns true if queue is empty , else returns false .

IsFull() : IsFull() is used to verify that queue is full or not .
It returns true if queue is full , else returns false . 

EnQueue(int value)  : EnQueue() is used to insert the data element at the rear end of queue. 
It takes one argument of type either  int or float or char . 
The precondition for EnQueue() is that queue should not be full . 

DeQueue() : DeQueue() is used to delete the data element from the front of the queue . 
it returns the value of deleted element to the main function . 
The precondition for DeQueue() is that queue should not be empty . 

 Implementation of Queue
Queue can be implemented with the help of static data structure as well as dynamic data structure . 
The detailed and simple explanation of queue implementation is discussed  in below two articles  .
  1. Queue using Array (Static)
  2. Queue using Linked List (Dynamic)

 Applications of Queue in Computer Science 

Queue finds many applications in Computer Science world . 
  1. In Operating System : Queue is used for process management and implementing Multiprogramming concepts in OS 
  2. Buffering the data or commands between processor and devices in system programming and application programming .