Comp 121 – Introduction to Data Structures

Comp 121 – Introduction to Data Structures. Spring 2000

Programming Assignment 2 -- Due March 9, 2000

Objective: To gain further experience in implementing abstract data types (ADT’s). To design and implement a non-trivial algorithm.

Goal. To implement the enhancedStack ADT as an object template in C++.

The enhanced stack abstract data type is specified as follows:

AbstractDataType enhancedStack{

Instances: finite collections of zero or more elements

Operations:

Create(n): Create an empty enhancedStack capable of holding n elements

Destroy( ): Erase an enhancedStack

IsEmpty( ): Return true if the enhancedStack is empty; false otherwise

IsFull( ): Return true if the enhancedStack is full; false otherwise

push(x): Insert the element x into the enhancedStack

top( ): Return the last element inserted into the enhancedStack

pop( ): Delete the last element inserted from the enhancedStack, and return this deleted element

Min( ): Return the smallest element in the enhancedStack

nextMin( ): Return the second-smallest element in the enhancedStack

}

You are to implement this ADT in the C++ programming language. I.e., you are to define a class template

template enhancedStack <class T>{

};

such that declarations (known as "instantiations" of the class template) of the form

enhancedStack <int> S1(10);

enhancedStack <myClass> S2(25);

would create an instance S1 of a enhancedStack capable of holding 10 integers, and an instance S2 of a enhancedStack that is capable of holding 25 myClass objects (where "myClass" is an object that you have previously defined).

Algorithms/ data structures. Implement your enhancedStack using what the text calls "formula-based representation." (I.e., use arrays rather than linked lists.) Your implementation must be Q (1) – i.e.,take constant time – per operation.

Rules for submitting this (and future) programs:

Recall that you are not permitted to work in groups – all your work must be your own, and you must attest to this in a signed comment that begins each program.

Include a (neatly typed – not handwritten) design plan. This design plan should contain a detailed description of all algorithms you use – in particular, the algorithms and data structures used to implement the min( ) and nextMin( ) methods.

Include some general comments on the structure and layout of your assignment.

Include a complete listing of all your code, input files, and output files

Your code must be appropriately commented – if we don’t understand your code with reasonable effort, you get no credit for it. Include comments on the "big-Oh" run-time complexity of all public methods.

Include a test plan detailing how you tested your ADT, and why you believe it is correct.

All of the above should be placed in an envelope with your name and student-ID on the outside, and submitted at the beginning of class on the due date. Submissions will not be accepted after 10 minutes have elapsed from the start of class – no late submissions will be accepted without documented reasons.