(******************************************************************)
(*                       FIFO QUEUE ADT                           *)
(*                (Array-based Implementation)                    *)
(******************************************************************)

CONST
  MaxQueue = 100;

TYPE
  QueueElementType = Char; (* or whatever is in the queue *)

  IndexType   = 1..MaxQueue;

  QueueType   = RECORD
    Elements : ARRAY[IndexType] OF QueueElementType;
    Front    : IndexType; (* index of slot preceding front *)
    Rear     : IndexType  (* index of slot containing rear *)
  END; (* QueueType *)

(*************************************************************)

PROCEDURE CreateQueue
  (VAR Queue : QueueType);

  (* Initialize Queue to empty state. *)

BEGIN (* CreateQueue *)

  Queue.Front := MaxQueue;
  Queue.Rear  := MaxQueue

END; (* CreateQueue *)

(**************************************************************)

PROCEDURE DestroyQueue
  (VAR Queue : QueueType);

  (* Remove all elements from Queue, leaving the queue empty. *)

BEGIN (* DestroyQueue *)

  Queue.Front := MaxQueue;
  Queue.Rear  := MaxQueue

END; (* DestroyQueue *)

(**************************************************************)

FUNCTION EmptyQueue
  (Queue : QueueType) : Boolean;

  (* Returns True if Queue is empty; returns False otherwise. *)

BEGIN (* EmptyQueue *)
  (* Queue is empty if Rear indicator = Front indicator. *)
  EmptyQueue := Queue.Rear = Queue.Front

END; (* EmptyQueue *)

(************************************************************)

FUNCTION FullQueue
  (Queue : QueueType) : Boolean;

  (* Returns True if Queue is full; returns False otherwise. *)

BEGIN (* FullQueue *)

  (* Queue is full if the next available rear position *)
  (* is equal to the front of the queue.               *)
  FullQueue := ((Queue.Rear MOD MaxQueue) + 1 = Queue.Front)

END; (* FullQueue *)

(**************************************************************)

PROCEDURE Enqueue
  (VAR Queue  : QueueType;
   NewElement : QueueElementType);

  (* Add NewElement to the rear of the queue. Assumes *)
  (* that the queue is not full.                      *)

BEGIN (* Enqueue *)

  (* Find the next rear position. Queue.Rear is the    *)
  (* index of the current rear of the queue. The queue *)
  (* may wrap around the end of the array.             *)
  Queue.Rear := (Queue.Rear MOD MaxQueue) + 1;

  (* Add new element to the rear of the queue. *)
  Queue.Elements[Queue.Rear] := NewElement

END; (* Enqueue *)

(*********************************************************)

PROCEDURE Dequeue
  (VAR Queue      : QueueType;
   VAR DeqElement : QueueElementType);

  (* Remove the front element from Queue and return it   *)
  (* in DeqElement. Assumes that the queue is not empty. *)

BEGIN (* Dequeue *)

  (* Update Queue.Front to access the front of the queue. *)
  (* Queue.Front is the index of the array slot preceding *)
  (* the front element in the queue. The queue may wrap   *)
  (* around the end of the array.                         *)
  Queue.Front := (Queue.Front MOD MaxQueue) + 1;

  (* Assign the front element of the queue to DeqElement. *)
  DeqElement := Queue.Elements[Queue.Front]

END; (* Dequeue *)

(****************************************************************)