Queue (First In First Out)

First In First Out

Applications: Job Scheduling

Queue ADT

objects: a finite ordered list with zero or more elements.
methods:
     for all queue Î Queue, item Î element,
              max_ queue_ size Î positive integer
     Queue createQ(max_queue_size) ::=
              create an empty queue whose maximum size is
              max_queue_size
     Boolean isFullQ(queue, max_queue_size) ::=   
              if(number of elements in queue == max_queue_size)
              return TRUE
              else return FALSE
     Queue Enqueue(queue, item) ::=
              if (IsFullQ(queue)) queue_full
             else insert item at rear of queue and return queue    

Queue ADT (cont’d)

Boolean isEmptyQ(queue) ::=
              if (queue ==CreateQ(max_queue_size))
              return TRUE
              else return FALSE
     Element dequeue(queue) ::=
              if (IsEmptyQ(queue)) return
              else remove and return the item at front of queue.

What is Queue ? Examples of Queue ?

1. Stores a set of elements in a particular order
2. Stack principle: FIRST  IN  FIRST  OUT
3. = FIFO
4. It means: the first element inserted is the first one to be removed
5. Example
   

The first one in line is the first one to be served

Real life examples

1. Waiting in line
2. Waiting on hold for tech support

Applications related to Computer Science

1. Threads
2. Job scheduling (e.g. Round-Robin algorithm for CPU allocation)