CSCI 203 Project #2

Doggie! (Doubly Linked Lists, Stacks, and Queues)

Purpose: This project is to practice with stacks, queues, and linked lists. In addition, you will gain experience building classes from other classes.

Description: You are to implement a program to play the very simple-minded game, Doggie. Doggie repeatedly asks the user what his doggie eats, and each string that is entered is pushed onto a stack, with two exceptions. If the user enters the string “grass”—well, everyone knows what happens when a doggie eats grass, right? It gets sick and up comes everything it has eaten, in the reverse order it ate it. (Sounds definitely like a LIFO stack to me…) So your program is to repeatedly get strings from the user and to push them onto the stack until the string “grass” is entered, at which time you should pop every item off the stack and print it, one item at a time. This should continue until the user types in the string “dog food”, at which time your program should exit. You should make sure that your string comparisons are not case sensitive, by the way.

Sounds simple, right? Well, there is one teensy bit of information I haven’t told you yet. Your stack that holds the strings should be a templated class that is implemented using two queues, as we discussed in class. These queues should be implemented as a templated class where each queue is composed of two stacks. Note that these will not be objects of the stack class you defined above. The stacks that make up the queue class should be implemented using two queues, which are not the same as the queues implemented above. Finally you should implement these queues using a templated doubly linked list class. All of these classes are (obviously) templated…so you have a templated doubly linked list class that you use to build a templated queue class which you then use to build a templated stack class. You use this stack class to implement a second templated queue class, and you use that queue class to build a second templated stack class, and this last stack class is the class you use for the Doggie game.

Here is some sample output:

Hi, what is your doggie’s name?

Bozo

What does Bozo eat?

a loaf of bread

What does Bozo eat?

a garbage truck

What does Bozo eat?

three clouds

What does Bozo eat?

grass

Oh, no, it looks like Bozo is getting sick! Ick...

Bozo barfs up three clouds

Bozo barfs up a garbage truck

Bozo barfs up a loaf of bread

It looks like Bozo is feeling better now...

What does Bozo eat?

dog food

Ugh! Bozo is insulted and runs away in a huff!

Turnin: You should turn in a zipped file containing your source file(s), the data file you used for the test, and a text file containing a screen capture of the output of your program running on the data file. You should also include a README file that describes any special or unique features of your program, as well as instructions as to how to compile and run it.

Hints: Work on one piece of this at a time, starting with the linked list class first. Get it working, and write some test scaffolding so that you can verify that all the list functions are working correctly before going any further! Once you have it working to your satisfaction, start on the first queue class. If you did a good job with your linked list, this should be just a few lines of code. Once you have the queue working, tested, and debugged to your satisfaction, then build the first stack class. Again, this should be just a few lines of code. After you have this tested and debugged, build and test your second queue class using this stack class, and finally implement your second stack class using the second queue class. After testing this extensively, you can write the Doggie main program to use this last stack class.