School of Engineering and Applied Science Department of Computer Science CSci 133 -- Algorithms and Data Structures I http://www.seas.gwu.edu/~csci133/spring04 Prof. Michael B. Feldman mfeldman@gwu.edu

This two-stage project depends mostly on Chapters 6 and 7 of Lewis & Chase, Java Software Structures.

An interesting variant of the FIFO queue is the traversable FIFO queue (TFIFO). This supports the same methods as the "ordinary" FIFO, with the added "feature" that the queue can be traversed (without being modified!) at any time. This can be done by adding iterator methods. In this project you'll develop a TFIFO using a linked-list implementation of the queue, and also an application that extends the capabilities of the Stratagem game program from earlier projects.

Part 1:

Develop and test a linked implementation of the QueueADT presented in Chapter 7. You will find the section 6.4, on linked stacks, useful.

Part 2:

Now use Part 1 as a starting point for a TFIFO class. Develop and test this.

Part 3:

Finally, let's go back to the Stratagem application. It would be nice to be able to replay a game -- that is, to store all the moves and ask the program to re-run the game, move by move, an arbitrary number of times, without asking the user to re-enter the moves. (For example, the user could just press RETURN to continue with the next move.)

Modify the application so the user can:

• quit the current game (without pressing ctrl-C)
• choose whether to play a new game or rerun the "memorized" game
• quit the program
  

This is an excellent application of the TFIFO:

• When the user is entering game moves, enqueue each valid move on a traversable queue;
• When the user requests a replay, traverse the queue and execute each move in turn

(end of project)