What to submit: For each program, you should discuss briefly how you designed it. This may be done by providing
a simple piece of pseudo-code, and/or describe your considerations, concerns, and the problems that you have
encountered during coding and debugging. For each program, you should turn in a hard-copy (i.e., printed version)
of your code (including the discussion) during class. Also, in each program, you should include appropriate
comment lines to describe the source code. Missing discussions and/or comment lines in the program will result in a
deduction on your grade for this assignment.
Plagiarism: If two or more submitted projects are identical, except for some minor variations, then a score of zero
will be assigned to all identical projects.
1. Write a class template for a linked-list implementation of a stack. The Stack class must have the same function
prototypes as the ones used in page 15 of Lecture 8, but with four additional functions: destructor, copy constructor,
overloaded assignment operator, and deepCopy. The private section shall only have one data member: a pointer
called top. Be sure to have the pointer of the last node (at the bottom of the stack) set to NULL at all times. (This
condition wasn't necessary in the linked-list implementation of the queue, because the back pointer signified the last
node but it is generally necessary in linked lists). At the top of the class implementation file, include iostream
(important because NULL is defined here) and use the std namespace.
2. Your task in this problem is to evaluate the performance of the vector and list containers of STL for various
operations (use integer values). In particular, you will measure the CPU time required for each container to perform
the following operations:
(i) Insert all the integers from 0 to 999,999 (one by one) into the back of the container.
(ii) Find the element with value 100,000 and place an iterator to point to that element (you have to manually
find the element even for the vector container).
(iii) Erase the element found in part (ii), using the erase function.
For each of the three tasks, output on the screen the CPU time (in seconds) required to complete the task for the two
different containers. In particular, perform each experiment 100 times, and output the average times (don't forget to
clear the containers before each run). Comment on the results and also include a screenshot of the output in your
report. To measure CPU time in C++, do the following:
(i) Define: time_t start,stop;
(ii) Just before the series of statements for which you want to measure the CPU time put: start=clock();
(iii) After the aforementioned statements put: stop=clock();
(iv) The CPU time in seconds is: double(stop-start)/CLOCKS_PER_SEC