Menu Close

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.
  • We can implement Queue in 2 ways
    • Static – Fixed size
    • Dynamic – Size varies