Exercises

Exercise 8.2

Observe that the task of ``popping'' a stack has been separated into two distinct operations pop and top. How would the DEFINITION MODULE of Fig. 8.1 be amended if a single operation pop_stack is to be provided which retrieves the top-most element of a stack and produces a new stack with the top-most element removed? Suppose an application requires the entire contents of a non-empty stack to be removed and displayed. This could be achieved as follows :

   WHILE NOT isempty(s) DO
      pop_stack(s,value);
      Write(value)
   END;

What is the corresponding Pascal-like code fragment using the specification of Fig. 8.1?

Exercise 8.3

Another widely used data structure is the queue which is a FIFO structure (first-in-first-out). The behaviour of a queue can be described in terms of the following set of operations :

• new :     an operation which creates an initial empty queue.
• add :     an operation which adds a data element to the end of an existing queue to produce a new queue.
• remove :     an operation which takes a queue as input and produces a new queue with the front-most (least-recently added) element removed.
• front :     an operation which takes a queue as input and returns the element at the front of the queue.
• isempty :     an operation which takes a queue as input and returns true if the queue is empty, false otherwise.

If the data elements of the queue are natural numbers, produce a Modula-2 DEFINITION MODULE Queues for the abstract data type. For example, the procedure remove will have the header

PROCEDURE remove(q : Queue) : Queue;

Demonstrate, by appropriate renaming of the operations (PROCEDURE names) and TYPE identifiers, that the abstract data types Stacks and Queues have the same syntax up to renaming.