CS14, Program 3

Assigned: May 8th, 2001

Due: May 16th, 2001, 10pm

 

Topics

 

·         Linked Lists

·         Stacks and Queues

·         Building classes from classes

·         Exception Handling

 

 

Stacks and Queues Revisited

 

In program 1, you wrote array based stacks and queues. In this program, you will use a List class to build linked-list based stacks and queues. The header files for the classes are essentially the same, with the exception that Q and S will not be pointers to chars but rather List objects. The methods will be composed of calls to the List methods.

Note that there is no longer a limitation on stack/queue size. You can leave both constructors in the class. Both should do the exact same thing, except that the size-specifying constructor should print a warning saying that the stack/queue size is not limited and that the size parameter will be ignored.

Stack/queue underflow should be dealt with by using exception handling (discussed in lab, or read about it in chapter 13 of Deitel). Stack/queue overflow really shouldn\'d5t happen, unless you exhaust all memory, in which case your program will crash anyway}

Recall that all operations on stacks and queues are O(1) (constant time) operations, but this is not necessarily true of all List operations. Be very careful which List methods you use so that the stack and queue operations are indeed O(1).

Consider adding a method or methods to the List class that will make Top() and Front() easier to write.

 

 

To do

 

- Use your list class, or download a working list.cc

- Change the headers of the stack and queue files to include list.h and to reflect that Q and S are List objects.

- write stack.cc and queue.cc, paying attention to the details listed above.

- test your classes, using the same test program you used for program 1 if you still have it, to see that they actually work the same as your array based stack and queue. Verify that the palindrome program gives the same results. This is for your own edification only; there is no need to turn in either a test main or a palindrome program.

- write two short programs that reads characters from a file and insert them into a data structure one by one and then extracts characters from the structure until it is empty. The first program should use a stack, the second a queue. Verify that your programs work on both the array based implementation and the linked list based one.

- Run these programs using as input the file lorax.txt (~10,000 characters) and the file hamlet.txt (~200,000 characters). You can either download these files, or use input redirections from my directory by typing (assume the executable is "run"

run < ~deganit/cs14/data/lorax.txt

at the prompt. What this command does is use the file instead of the keyboard as the input stream, without having to hardwire the filename into the program. (You can also redirect output by typing

run > outputfile

the output will be written to the file outputfile instead of to the screen.)

- Time the programs, once using the array based implementation, once using the linked list one, using the input files above. You should have four separate runs. To time a program, proceed the executable name with the command "time", as in (assume the executable is "run" and the data is in "inputfile" )

time run < inputfile

the output of a time command has the format

0.000u 0.010s 0:01.04 0.9% 0+0k 0+0io 139pf+0w

The first number is the user time, the second is the system time used, which is the number of interest here. You can safely ignore the rest. Short programs usually don't even register a time, which is why we are using large file inputs when timing these programs.

- Are the running times comparable for the two implementations? How do the running times for the two files compare? Summarize your results briefly in a file called README, which you should turn in with your program.

 

 

 

 

What to turn in

 

- stack.h, stack.cc, queue.h, queue.cc, list.h and list.cc

- README file that gives the results of timing your program.