14.3 Queues

When data is organized in a list (or an array), one can get access to any one of the items in the structure. However, if data structures are to mirror real-life situations, this kind of access may not always be desirable.

Consider for instance the problem of simulating something like a cashier's lineup. Here, new data items are added at one end of the line, but they are only served at the other, in order of their addition to the line. This is termed a first-in-first-out data structure.

Example:

Action		Resulting Queue 
A arrives		A
B arrives		AB
C arrives		ABC
service  		BC
D arrives		BCD
service  		CD
A first-in-first-out data structure is called a queue.

One would probably implement a queue in such a way that the only operations on it were, say, Init, Destroy, Full, Empty, Enqueue (add to queue), and Serve. This would prevent access to any but the end of the queue for adding and the beginning for serving (removing an item). Full would be used to check the status of the queue before attempting to add, and Empty to check before attempting to serve.

Init would create an empty queue, and Destroy would terminate it (giving back all the memory it used in the dynamic allocation).

Here, for example is a module to define and implement a queue for text items:

DEFINITION MODULE TextQueues;

(* a simple text queue of specified size
  by  R. Sutcliffe
  last modified 1995 05 29  *)

TYPE
  Queue;   (* details in implementation *)
  ActionProc = PROCEDURE (CHAR);

PROCEDURE Init (maxSize : CARDINAL) : Queue;
(* Pre: none
   Post: Establish a text queue that can enqueue at most maxSize characters.  *)

PROCEDURE Destroy (q : Queue);
(* Pre: q is a previously established queue.  
   Post: any memory previously allocated to q is now returned. *)

PROCEDURE Full (q : Queue) : BOOLEAN;
(* Pre: q is a previously established queue.  
   Post: if the number of active items in the queue equals the maxSize used when Init was called, returns TRUE; otherwise returns FALSE. *)

PROCEDURE Empty (q : Queue) : BOOLEAN;
(* Pre: q is a previously established queue.  
   Post: if the number of active items in the queue is zero, returns TRUE; otherwise returns FALSE. *)

PROCEDURE Enqueue (q : Queue; item : CHAR);
(* Pre: q is a previously established queue.  
   Post: if the number of active items in the queue is less than the maxSize used when Init was called, the given character is added to the queue; otherwise no action is taken. *)

PROCEDURE Serve (q : Queue; VAR item : CHAR);
(* Pre: q is a previously established queue.  
   Post: if the number of active items in the queue is greater than the zero, a character is removed from the queue and returned on a first-in-first-out basis; otherwise no action is taken. *)

PROCEDURE Traverse (q : Queue; Proc : ActionProc);
(* Pre: q is a previously established queue.  
   Post: The action specified by Proc is taken on each item in the queue from the head to the tail without affecting the queue itself. *)

END TextQueues.

This particular specification envisions a maximum size for a queue defined when the queue is first created. It also has a procedure that allows a client application to "walk" or "traverse" down the queue and do something with each item without affecting the queue itself. The "something" that is done depends on the procedure that is passed.

In the implementation, Queue must be redefined as a pointer to a data structure containing information as to the size of the queue, a pointer to the actual data, the number of active items, and a pointer to indicate the position in the queue for enqueing (head) and for serving (tail.) Init must create and initialize one of these structures and set aside enough memory for maxSize characters. Enqueue must enter the supplied character into the queue and adjust the counter and enqueing position. Serve must remove and return the character at the serving position, adjust the serving position and the count. One possible implementation of this queue uses a dynamic array to hold the characters. If in adjusting the count, one goes past the end of the structure, the number must be wrapped to the beginning (if possible.) If the two counters collide, the queue is either full or empty, depending on which catches up with which. Here, though, these conditions are kept track of by the number of items that are currently in the queue.

Because it would be somewhat inefficient to implement this by dynamically allocating a separate piece of memory for each character to be enqueued, the Init procedure has been specified to take sufficient memory for the maximum number of items that can be enqueued. Here is the implementation:

IMPLEMENTATION MODULE TextQueues;

(* a simple text queue of specified size
  by  R. Sutcliffe
  last modified 1995 05 29  *)

FROM SYSTEM IMPORT
  ADDRESS, ADDADR;
FROM Storage IMPORT
  ALLOCATE, DEALLOCATE;

TYPE
  Queue = POINTER TO QueueData;
  QueueData = 
    RECORD
      size : CARDINAL;
      numberActive: CARDINAL;
      head, tail : CARDINAL;
      dataPtr : ADDRESS;
    END;
  CharAdr = POINTER TO CHAR;

PROCEDURE Init (maxSize : CARDINAL) : Queue;
VAR
  q : Queue;
BEGIN
  NEW (q);  (* set up a queue record *)
  q^.size := maxSize;
  q^.numberActive := 0;
  q^.head := 0;
  q^.tail := 0;
  ALLOCATE (q^.dataPtr, SIZE (CHAR) * maxSize);
  IF q^.dataPtr = NIL (* couldn't get memory for data *)
    THEN
      DISPOSE (q);
    END;
  RETURN q;
END Init;

PROCEDURE Destroy (q : Queue);
BEGIN
  DEALLOCATE (q^.dataPtr, SIZE (CHAR) * q^.size); (* data *)
  DISPOSE (q); (* and queue info *)
END Destroy;

PROCEDURE Full (q : Queue) : BOOLEAN;
BEGIN
  IF q^.numberActive = q^.size
    THEN
      RETURN TRUE
    ELSE
      RETURN FALSE
    END;
END Full;

PROCEDURE Empty (q : Queue) : BOOLEAN;
BEGIN
  IF q^.numberActive = 0
    THEN
      RETURN TRUE
    ELSE
      RETURN FALSE
    END;
END Empty;

PROCEDURE Enqueue (q : Queue; item : CHAR);
VAR
  ptr : CharAdr;
BEGIN
  IF NOT Full (q)
    THEN
      ptr := ADDADR (q^.dataPtr, q^.tail * SIZE (CHAR));
      ptr^ := item;
      INC (q^.numberActive);
      q^.tail := (q^.tail + 1) MOD q^.size;
    END; (* does nothing if full *)
END Enqueue;

PROCEDURE Serve (q : Queue; VAR item : CHAR);
VAR
  ptr : CharAdr;
BEGIN
  IF NOT Empty (q)
    THEN
      ptr := ADDADR (q^.dataPtr, q^.head * SIZE (CHAR));
      item := ptr^;
      DEC (q^.numberActive);
      q^.head := (q^.head + 1) MOD q^.size;
    END;  (* does nothing if empty *)
END Serve;

PROCEDURE Traverse (q : Queue; Proc : ActionProc);
VAR
  ptr : CharAdr;
  pos : CARDINAL;
BEGIN
  IF NOT Empty (q)
    THEN
      pos :=  q^.head; (* start at head of queue *)
      REPEAT
        ptr := ADDADR (q^.dataPtr, pos * SIZE (CHAR));
        Proc (ptr^); (* do whatever we were told to *)
        INC (pos);
        IF pos = q^.size
          THEN  (* wrap around if necessary *)
           pos := 0;
          END;
      UNTIL pos = q^.tail;
  END;
END Traverse;

END TextQueues.

If some other abstract data type is to be enqueued using this approach, another library module must be written. The example below has the predicates removed to make it more compact. It is written in the semi-generic style of the list module in the previous section.

DEFINITION MODULE anAdtQueues;

(* a simple semi-generic queue 
  by  R. Sutcliffe
  last modified 1995 05 29  *)

FROM ItemADT IMPORT
  ItemType;
TYPE
  DataType (* local name *) = ItemType;
  ActionProc = PROCEDURE (DataType);
  Queue;
  
PROCEDURE Init (VAR q : Queue);
PROCEDURE Destroy (q : Queue);
PROCEDURE Full (q : Queue) : BOOLEAN;
PROCEDURE Empty (q : Queue) : BOOLEAN;
PROCEDURE Enqueue (q : Queue; item : DataType);
PROCEDURE Serve (q : Queue; VAR item : DataType);
PROCEDURE Traverse (q : Queue; Proc : ActionProc);

END anAdtQueues.

This time, a singly linked approach is used to the implementation. Here, a queue is only full if no more memory can be obtained for the data node. Since it is necessary to be able to check that fact ahead of time by calling Full, the space for the next data node is obtained after the current one has been linked in. The very first one is obtained in the body of the module. If the last obtained data node pointer is NIL, then all queues established by this module are full (so, the parameter on Full could have been left out).

IMPLEMENTATION MODULE anAdtQueues;

(* a simple semi-generic queue 
  by  R. Sutcliffe
  last modified 1995 05 29  *)

FROM Storage IMPORT
  ALLOCATE, DEALLOCATE;
  
TYPE
  DataPtr = POINTER TO DataNode;
  DataNode =
    RECORD
      data : DataType;
      toPoint : DataPtr; (* single node linking *)
    END;
  Queue = POINTER TO QueueData; 
  QueueData = (* each queue has this data *)
    RECORD
      head, tail : DataPtr;
    END;
VAR
  nextItem : DataPtr;
    (* a global for reserving space ahead of time *)

PROCEDURE GetNextItemSpace;
BEGIN
   NEW (nextItem);
END GetNextItemSpace;
    
PROCEDURE Init (VAR q : Queue);

BEGIN
  NEW (q);  (* set up a queue record *)
  IF q # NIL
    THEN
      q^.head := NIL;
      q^.tail := NIL;
    END;
END Init;

PROCEDURE Destroy (q : Queue);
VAR
  dummy : DataType;  (* not going anywhere, just killing them *)
BEGIN
  IF NOT Empty (q)
    THEN
      REPEAT
        Serve (q, dummy);
      UNTIL Empty (q);
    END;
  DISPOSE (q);
END Destroy;

PROCEDURE Full (q : Queue) : BOOLEAN;
(* whenever the last call to GetNextItemSpace returned NIL, all lists are full. *)

BEGIN
 RETURN  (nextItem = NIL);
END Full;

PROCEDURE Empty (q : Queue) : BOOLEAN;
BEGIN
  IF q^.head = NIL
    THEN
      RETURN TRUE
    ELSE
      RETURN FALSE
    END;
END Empty;

PROCEDURE Enqueue (q : Queue; item : DataType);
BEGIN
  IF NOT Full (q)
    THEN
      (* use global nextItem already obtained *)
      nextItem^.data := item;
      nextItem^.toPoint := NIL;
      IF Empty (q) (* i.e. before this *)
        THEN (* change head *)
          q^.head := nextItem
        ELSE (* chain old tail to new one *)
          q^.tail^.toPoint := nextItem;
        END;
     q^.tail := nextItem; (* always *)
     GetNextItemSpace; (* for next time; if fails, will show full *)
    END; (* does nothing if full *)
END Enqueue;

PROCEDURE Serve (q : Queue; VAR item : DataType);
VAR
  temp : DataPtr;
BEGIN
  IF NOT Empty (q)
    THEN
      temp := q^.head;
      q^.head := q^.head^.toPoint;
      IF NOT Full (q)
        THEN
          DISPOSE (temp)
        ELSE
          nextItem := temp;
        END;
    END;  (* does nothing if empty *)
  IF Empty (q) (* i.e. now empty *)
    THEN
      q^.tail := NIL;
    END;
END Serve;

PROCEDURE Traverse (q : Queue; Proc : ActionProc);
VAR
  ptr, next : DataPtr;
BEGIN
  IF NOT Empty (q)
    THEN
      ptr :=  q^.head; (* start at head of queue *)
      REPEAT
        next := ptr^.toPoint;
        Proc (ptr^.data); (* do whatever we were told to *)
        ptr := next;
      UNTIL ptr = NIL;
    END;
END Traverse;

BEGIN
  GetNextItemSpace; (* do one ahead of time *)
END anAdtQueues.

The very simple test harness below was used to check the operation of this library. Note that the library itself would be renamed according to the data type it was importing. The procedure passed to traverse would also depend on the data being used. Perhaps that procedure too could be placed in the ADT library and imported to the queue library.

MODULE QueueTest;
(* crude test program to test the queue library with the cardinal ADT as imported to anAdtQueues from ItemADT 
by R. Sutcliffe  modified 1995 05 29 *)

FROM STextIO IMPORT
  WriteString, WriteLn, ReadChar, WriteChar, SkipLine;  
FROM SWholeIO IMPORT
  WriteCard;
FROM anAdtQueues IMPORT
  Queue, Init, Destroy, Enqueue, Full, Empty, Traverse, Serve;
  
VAR
  q : Queue;
  n : CARDINAL;
  ch : CHAR;
  
PROCEDURE WriteItem (card: CARDINAL);
(* a procedure to pass as a parameter in the next procedure *)
BEGIN
  WriteCard (card, 0);
  WriteChar (",")
END WriteItem;

PROCEDURE WriteCardQueue (q : Queue); 
BEGIN
   Traverse (q, WriteItem);
   WriteLn;
END WriteCardQueue;

BEGIN (* main *)
  Init (q);
  n := 1;
  Enqueue (q, n);
  WriteCardQueue (q);
  n := 2;
  Enqueue (q, n);
  WriteCardQueue (q);  
  n := 1000;
  Enqueue (q, n);
  WriteCardQueue (q);
  Serve (q, n);
  WriteCardQueue (q);
  n := 2000;
  Enqueue (q, n);
  WriteCardQueue (q);
  Serve (q, n);
  WriteCardQueue (q);
  n := 30000;
  Enqueue (q, n);
  WriteCardQueue (q);

END QueueTest.

The results of this test are shown below:

** Run log starts here **
1,
1,2,
1,2,1000,
2,1000,
2,1000,2000,
1000,2000,
1000,2000,30000,

In the next two chapters, more advanced techniques will be discussed to allow the concept of the queue to be abstracted without reference to any particular data type that is to be enqueued and served.


Contents