Test 2- Review

Four ADTs

• list, stack, queue, set
• You should know ADT definitions
• Questions will be: Write a function that accepts stack of integers by reference with maximum size equal to 20 stack<int,20> as an argument and returns the second item on the stack (leave the stack intact).

int second_item(stack<int,20>& s)

{

int temp = s.top();

s.pop();

int return_value = s.top();

s.push(temp);

return return_value;

}

• Create a descendant of an existing data structure with an additional function
• A special_stack that has an additional function second() that returns the item at the top of a stack leaving the stack unchanged.

template <class T,int M>

class special_stack : public stack<T,M>

{

public:

T second();

};

template <class T,int M>

int special_stack<T,M>::second ()

{

T temp = top();

pop();

T return_value = top();

push(temp);

return return_value;

}

• Descriptive questions such as compare and contrast stacks/queues, set/list, linked/contiguous of list
• Given a code that uses some of the operations of ADTs what will be the time requirement using big Oh