generic
   type Element_Type is private;
package Queue is

   -- This package implements FIFO queue, a data structure in which 
   -- elements are added to the rear and removed from the front; 
   -- a "first in, first out" (FIFO) structure.

   type Queue_Type (Max_Size : Positive) is tagged limited private;

   OVERFLOW  : exception;
   UNDERFLOW : exception;

   ----------------------------------------------------------------------------
   procedure Clear (Queue : in out Queue_Type);
   -- Purpose        : Remove all elements from the queue
   -- Preconditions  : None
   -- Postconditions : Queue is empty; it contains no elements

   ----------------------------------------------------------------------------
   procedure Enqueue (Queue : in out Queue_Type;
                      Item  : in     Element_Type);
   -- Purpose        : Adds Item to the rear of Queue
   -- Preconditions  : None
   -- Postconditions : Queue = original Queue with Item added to its rear
   -- Exceptions     : OVERFLOW  Raised on attempt to Enqueue an element onto
   --                            a full queue.  Queue is unchanged.

   ----------------------------------------------------------------------------
   procedure Dequeue (Queue : in out Queue_Type;
                      Item  :    out Element_Type);
   -- Purpose        : Removes the front element from Queue and returns it
   -- Preconditions  : None
   -- Postconditions : Queue = original Queue with front element removed
   --                  Item  = front element of original Queue
   -- Exceptions     : UNDERFLOW  Raised on attempt to dequeue an element from 
   --                             an empty Queue.  Queue remains empty.

   ----------------------------------------------------------------------------
   function Full (Queue : in Queue_Type) return Boolean;
   -- Purpose        : Tests whether a queue is full.  A queue is full when
   --                     no more elements can be enqueued into it
   -- Preconditions  : None
   -- Postconditions : Full = (no more elements can be enqueued into Queue)

   ----------------------------------------------------------------------------
   function Empty (Queue : in Queue_Type) return Boolean;
   -- Purpose        : Tests whether a queue is empty (contains no elements)
   -- Preconditions  : None
   -- Postconditions : Empty = (Queue is empty)

private

   type Queue_Array is array (Positive range <>) of Element_Type;
   type Queue_Type (Max_Size : Positive) is tagged limited
      record
        Count : Natural  := 0;         -- Number of items in the queue
        Front : Positive := 1;         -- Pointer to first item in the queue
        Rear  : Positive := Max_Size;  -- Pointer to last item in the queue
        Items : Queue_Array (1..Max_Size);  -- The element array
      end record;

end Queue;