Exercise Sheet 4: Stacks of Rats

1. A Cyclic Queue of Strings

   In the DAT Notes we consider a basic block implementation of a queue in which the block was eroded with use. To overcome the problem of erosion we also considered a cyclic block implementation. You might like to try out an interactive demonstration of (a slight variation of) such an implementation.

   Using the Notes as a guide, write a cyclic version (QueueStringCyclic) of your queue of strings. Again this should implement the QueueString interface. Test it using the PrimeMinisters program, again with a block of size 5. How does this compare with the non-cyclic version?

2. Block Implementation of a Stack

   Write a block implementation of a character Stack, called StackCharBlock. Your stack should contain the following public methods:

   1. StackCharBlock(s): create an empty stack of size s
   2. isEmpty(): return true if the stack is empty, false otherwise
   3. isFull(): return true if the stack is full, false otherwise
   4. push(c): push character c onto the top of the stack, or throw an Overflow exception if the stack is full
   5. peek(): return the character on top of the stack, or throw an Underflow exception if the stack is empty
   6. pop(): remove and return the character on the top of the stack, or throw an Underflow exception if the stack is empty

   Your Stack must implement the interface DAT.StackChar. Your Stack must also be fully documented using javadoc comments.

   Hint: Look back at your block implementation of a queue and consider how a queue and a stack differ.

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

   datlab Spot Check

   You should submit your StackCharBlock.java program to the datlab system for checking. This is worth 3 lab marks if submitted prior to the deadline.

3. The Reversal Program

   Now that you have a Stack ADT you can try out the ADT version of the Reversal Program discussed in the Notes. Some code for the reversal program can downloaded from the DAT source directory. Copy the program and use your own stack to try it out.

   Note: A common source of error is not being clear in your program about which class to use if there is more than one version in your classpath. If you have downloaded QueueCharBlock in the previous exercise and still have that in your project, you need to be clear in your code to tell the compiler whether you wish to use that version of the DAT package version. If you are using a local version don't import the DAT package version. If you wish to explicitly use the DAT package version you can specify DAT.QueueCharBlock. To save yourself problems it is better not to keep your own copies of classes in that are in the DAT package.

4. Challenge: Rats Galore!

   The rat in the maze in Exercise 2 searches for the finish using a depth-first search. If follows a single path until it can't go any further, then backtracks looking for an alternative route. As discussed in the associated references, this is ideally implemented using a stack.

   The aim of this exercise is to implement a kind of breadth-first search. To do this we will use multiple rats, and a queue.

   Modify the Maze program so that it implements the following two steps.

   1. Initialisation

      Make a modified version of your Queue for holding Points. Start with a rat on the start (S) square, and the Point that the rat is on in the Queue.

   2. Loop

      In each iteration do the following. Take the first rat (Point) from the front of the queue. Look at each of the four (or fewer at edges) adjacent squares in turn. If the square is the finish square place a rat in that square and halt. Otherwise, if the square is empty and has not been visited (that is, the array contains a zero), put a new rat in that square, facing in the direction required to reach that square, and add the new rat's point to the end of the queue. Once all adjacent squares have been processed, remove the current rat and replace the square with a visited (red) tile and change the grid to show that the square has been visited.

   You should see a wave of rats spreading across the maze like a ripple in a pond, with the wave front bending around walls etc. Try it with quite sparse mazes, and with quite dense mazes.