Question 1. You are given two STL lists X and P where P is already in sorted order. Write a valid C++ function printPositions(X, P ) that prints the elements in X specified by P . For example, if P = 0, 2, 5, 6, the elements in positions 0 (head of the list), 2, 5, and 6 in X are printed. You may use only the public STL container operations. Also specify the running time of your algorithm using Big-Oh notation.

Hint: You may wish to use iterators while keeping track of the position of items being iterated through.

Question 2. Given two unsorted STL lists X and P , write a valid C++ function intersection(X, P ) that returns a new list that contains the elements common to both X and P . For example, if X = 5, 2, 1, 4 and P = 4, 5, 7; your algorithm should return a new list containing 5 and 4 (order is not important). Also specify the running time of your algorithm using Big-Oh notation. Hint: As the lists are unsorted, a straightforward algorithm would need a double for loop.

Question 3. For the Vector class available on Blackboard, add an iterator insert(iterator pos, const Object & x) method. Note to move the iterators (which are really just pointers here) around, you need to add to them sizeOf(Object). For example, pos += sizeOf(Object); lets you examine the next item in the Object array.

Question 4. Verbally describe how two different stacks can be implemented using a single array.

Question 5. Write a stack class using two STL lists. Naturally, a single STL list is more than enough to represent a stack. However, you are only limited to the following STL list methods:

(a) void push back(const Object & x); //adds x to the end of list (b)void pop front(); //removes the object at the front of the list (c)Object & front(); //returns the object at the front of the list (d)bool empty() const; //true if empty container

Limited to these methods alone, our STL list essentially becomes a queue (enqueue is basically push back while dequeue is a combination of front and pop front). At the minimum, your stack class needs to have the following:

(a) An STL list is stored as an instance member of the stack class. You can think of this main list as storing your stack.

(b) A pop method that returns an Object at the top of the stack.

(c) A push method that takes an Object and places it at the top of the stack.

(d) If your list is empty, your pop method should throw an exception (any exception will do).

(e) Inside your push method, you can create a temporary list. As you are only limited to placing items at the back of your list (enqueue / push back), you can use this temporary list as storage to help move items from your main list to this list, add the new item to your main list, and then move back the items from the temporary list back to your main list.

Attachment:- Vector.rar