home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS - Coast to Coast / simteldosarchivecoasttocoast.iso / pcmag / vol9n04.zip / QUEUES.PAS < prev    next >
Pascal/Delphi Source File  |  1990-01-22  |  3KB  |  124 lines
  1. QUEUES.PAS
  2.  
  3. UNIT queues;
  4. (* Turbo Pascal 5.5 program *)
  5.  
  6. (**********************)
  7. (**)    INTERFACE   (**)
  8. (**********************)
  9. TYPE
  10.   GenericItem = OBJECT          {This object is nothing}
  11.     DESTRUCTOR done; virtual;   {by itself, but you can}
  12.   END;                          {make ANY other object }
  13.                                 {a descendant of it.   }
  14.  
  15.   ItemPtr = ^GenericItem;
  16.   ItemList = ^ItemNode;
  17.   ItemNode = RECORD
  18.     item : ItemPtr;
  19.     next : ItemList;
  20.   END;
  21.  
  22.   queue = OBJECT (GenericItem)
  23.     front, rear : ItemList;
  24.     length, maxlength : Word;
  25.     CONSTRUCTOR Init;
  26.     PROCEDURE MakeNull;
  27.     PROCEDURE enqueue(I : ItemPtr);
  28.     FUNCTION dequeue : ItemPtr;
  29.     FUNCTION empty : boolean;
  30.     FUNCTION GetLength : Word;
  31.     FUNCTION GetMax : Word;
  32.     DESTRUCTOR done; virtual;
  33.   END;
  34.  
  35. (**********************)
  36. (**) IMPLEMENTATION (**)
  37. (**********************)
  38.  
  39.   DESTRUCTOR GenericItem.done;   BEGIN END;
  40.  
  41.   CONSTRUCTOR queue.Init;
  42.   { To initialize a queue, create a "front" pointer
  43.     for it and set the "rear" pointer to the same
  44.     as the front.  Note that the actual queue of
  45.     items starts at "front^.next" -- "front" is
  46.     just a header node }
  47.   BEGIN
  48.     New(front);
  49.     front^.next := NIL;
  50.     Front^.item := NIL;
  51.     rear := front;
  52.     length := 0;
  53.     maxlength := 0;
  54.   END;
  55.  
  56.   PROCEDURE queue.MakeNull;
  57.   { To empty a queue, dispose of nodes until
  58.     the front of the line equals the rear }
  59.   VAR P : ItemList;
  60.   BEGIN
  61.     WHILE front <> rear DO
  62.       BEGIN
  63.         P := front;
  64.         front := front^.next;
  65.         IF P^.item <> NIL THEN
  66.           dispose(P^.item, done);
  67.         dispose(P);
  68.       END;
  69.   END;
  70.  
  71.   PROCEDURE queue.enqueue(I : ItemPtr);
  72.   { To enqueue an item, add it to the rear of the queue }
  73.   BEGIN
  74.     Inc(length);
  75.     IF length > maxlength THEN maxlength := length;
  76.     New(rear^.next);
  77.     rear := rear^.next;
  78.     rear^.item := I;
  79.     rear^.next := NIL;
  80.   END;
  81.  
  82.   FUNCTION queue.dequeue : ItemPtr;
  83.   { To dequeue an item, return the contents of the
  84.     frontmost node (the one after the "front" header),
  85.     advance the front pointer, and dispose of the
  86.     previous front }
  87.   VAR P : ItemList;
  88.   BEGIN
  89.     IF empty THEN dequeue := NIL
  90.     ELSE
  91.       BEGIN
  92.         dequeue := front^.next^.item;
  93.         P := front;
  94.         front := front^.next;
  95.         front^.item := NIL;
  96.         dispose(P);
  97.         Dec(length);
  98.       END;
  99.   END;
  100.  
  101.   FUNCTION queue.empty : boolean;
  102.   BEGIN  empty := front = rear;  END;
  103.  
  104.   FUNCTION queue.GetLength : Word;
  105.   BEGIN  GetLength := length;  END;
  106.  
  107.   FUNCTION queue.Getmax : Word;
  108.   BEGIN  Getmax := maxlength;  END;
  109.  
  110.   DESTRUCTOR queue.done;
  111.   { This procedure calls MakeNull to dispose
  112.     all of the nodes except "front", then
  113.     gets rid of "front" as well }
  114.   BEGIN
  115.     MakeNull;
  116.     dispose(front);
  117.   END;
  118.  
  119. END.
  120.  
  121.  
  122.  
  123.  
  124.