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.