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
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.