Homework 2 - Due via Electronic Turnin Thursday, February 5 at 8:00 pm
80 points total
Updated Feb 1 at 12am - Changed function name to be more clear in 6 and 7
This homework will be turned in electronically. For the homeworks only
you will need to turn in
either a postscript file or a pdf (but this does not mean that you can't
still use Word if you want to). Please do not turn in
a Word document (we don't want any viruses =). It would be wonderful
if you did not do the homework in Word but rather learned LaTex or DIA,
however, Word is just fine as well. Click
here for information on creating postscript and pdf files.
1. (10 pts) Show how to implement a queue using two stacks. Describe the Enqueue
and Dequeue functions. You may assume the Stack has the functions Push,
Pop, and Empty. You do not actually have to write code, you may just describe
the method and use pictures, but be sure you are clear.
2. (10 pts) For each part, specify what type of data structure would best be used
for the following situation (list, stack, or queue).
a) Customers at a grocery store waiting to pay for their groceries.
b) Hansel and Gretel leave their home and traverse a path dropping breadcrumbs
at particular locations on the way. They then want to use their breadcrumbs
to find their way home (using the reverse path)
c) A bank keeps track of their customer accounts
d) A library stores the information about each book they own
e) Students wait at the Cashier to pay their tuition
3. (10 pts) Write Enqueue and Dequeue (Dequeue will return the item dequeued via a
reference parameter to the function)
for an inefficient queue, where the items are stored
in an array in such a way that the queue's head is always at location 0 and
the queue's tail is always at location currentSizeOfQueue - 1.
4. (10 pts) Exercise 1 on page 426 in your book.
5. (5 pts) Write a templated function to determine the minimum of two variables
of the template type.
6. (15 pts) Define a class template for an array based implementation of the ADT stack.
Implement the member functions push, pop (does not return item), getTop,
and empty. (Remember the constructor and destructor)
7. (20 pts) Define a class template for a pointer based implementation of the ADT stack.
Implement the member functions push, pop (does not return item), getTop,
and empty. (Remember to declare your node class as well) (Remember the
constructor and destructor)