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