DS – Queue Data Structure

Queue:

• Queue is linear data structure
• It follows First in First out (FIFO) rule.
• Inserting elements from one end called “REAR”.
• Deletions from another end called “FRONT”.

Note: Front is fixed in Queue

Queue ADT:

• ADT(Abstract Data Type) is the represents all the specifications of Queue.
• Queue must be implements under the specifications as follows.
  • Enqueue: Insert an element if the queue is not full
  • Dequeue: Deletes an element if the queue is not empty
  • IsEmpty: Check whether the queue is empty or not
  • IsFull: Check whether the queue is full or not
  • Peek: Returns the first element of queue but not remove the element.

Applications of Queue:  The basic application of Queue is OS process scheduling. Queue is used when applications process immediately, but have to be processed in First in First Out order.

1. Breadth First Search.
2. CPU scheduling
3. Disk Scheduling.
4. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free.

Note: We can implement Queue in 2 ways

• Static Queue – Fixed size
• Dynamic Queue – Size varies

Static Queue:

• We can use simple array with fixed size.
• All operations need to perform using 2 variables Front and Rear.
• Front is always pointing to Front location that is 0 index.

Declaration of stack as follows: