Exercise Sheet 6: Cycling to Work

1. Linked Implementation of a Stack

   You can find an animated linked implementation of a Stack ADT that you can try out at here.

   Write a recursive (linked) implementation of a Stack of characters, called StackCharLinked. Your stack should implement the DAT.StackChar interface (that is, the StackChar interface in the DAT package). Note that while the interface allows for an Overflow exception to be thrown by the push method, this has been included for the block representation, and there is no need for your linked implementation to throw one.

   Hint: Look back at the basic linked list class covered in the DSA Notes. The Stack uses a similar structure. (Use appropriate variable names for the stack however.)

   Write a test program that tries out each operation to satisfy yourself that you stack works correctly.

2. Basic Performance Comparisons

   Topic 6 of the DAT Notes introduces a basic method of performance analysis for ADT operations using some simple timing assumptions.

   Carry out a basic performance analysis of your two Stack implementations. Under what conditions do the operations have constant time performance?

3. Counting while Cycling

   In an earlier exercise you implemented a cyclic queue of strings using indices to the first and last items. As discussed in the DAT Notes, this requires increasing the size of the block in order to differentiate between an empty queue and a full queue.

   An alternative solution suggested in the Notes was to keep an index to the first item, along with a variable, say count, that stores the current size of (number of items in) the queue. Thus, for example, when an item is inserted, the count will increase by 1.

   • Write a cyclic version (QueueCharCyclic) of a queue of characters using an index, called first and an item count, called count. These should be the only incides (last is no longer needed). When you enqueue an item, for example, the position in the array should be calculated from first and count. It is your job to work out how to calculate the correct position.

     Your ADT should implement the DAT.QueueChar interface. Test and document your code.

   DAT Spot Check

   You should submit your QueueCharCyclic code for checking.

   [3 Lab Marks]

4. Unbounded Cycling

   An (unbounded) queue can be implemented cyclically based on a linked list - rather than referencing "null", the last item's successor references the beginning of the queue. While this is not necessary to prevent erosion, it does mean that rather than having references to the beginning and the end of the queue, only a single reference is needed.
   • Implement a queue (QueueLinkedCyclic) using a cyclic, linked representation. Ensure that all operations have constant time performance.

     Write a test program to ensure that it works correctly.