1. Double-Ended Queues

Implement a double-ended queue data structure (often called a dequeue). A dequeue is a data structure supporting the operations push_front(int), push_back(int), pop_front(), pop_back(). A dequeue is supposed to work like a queue except you are allowed to pop elements from both sides and push elements on both sides. For example push_front(1), push_front(2), push_front(3), pop_back() should return 1. pop_front() should return 3. Another way to imagine this data structure is as two stacks sharing their bottom. If you only use push_front and pop_front, the data structure should behave exactly like a stack (similarly if you use only push_back and pop_back).

• Implement a class for a dequeue. Assume that the user supplies you with a fixed maximum size at construction (i.e. no need to make dequeues that resize)
• Also, overload the << operator so that it is possible for the user to print the entire contents of a dequeue (useful for debugging)
• Submit a header file named dequeue.h, an implementation file named dequeue.cpp and a test program named use_dequeue.cpp

Note: The space and time efficiency of your implementation will certainly have an impact on your grade.

2. Resizing Efficiently

Recall our implementation of a stack that expands to hold more data. We followed the approach of doubling the available space whenever we run out of storage.

• Multiplying the size by 2 seems a little arbitrary. Why not triple the size, or why not increase size by 50%? Discuss what are the pros and cons of each solution. How would you pick an appropriate factor for expansion? The expansion factor is the number c such that when space runs out we re-allocate the array to c*size.

Another observation is that in some cases the stack could hold a large number of elements for only a short time after which most of them are popped and the stack is mostly empty. (Think of 1000 pushes, followed by 950 pops. followed by a sequence of 10000000 alternating pushes and pops. For the largest part of its lifetime the stack needs around 50 positions, but it will always have size at least 1000). This wastes space, so an idea would be to pick a shrinkage factor d. Whenever elements < (1/d)size (i.e. less than 1/d of the array is in use) we will shrink our storage to a smaller size

• What should be the new size we select? Does shrinking to new_size = (1/d)size make sense? How about new_size = size - 10? Explain. What are the trade-offs?
• Does it make sense to set d< c? Explain.
• Does it make sense to set d=c? In particular, consider the following strategy: if the array is full, double its size. If the array uses less than half its space shrink its space in half. Evaluate its efficiency. How long will a sequence of n operations take in the worst case and why?

Note: This is an essay question. Think about it and submit a txt or pdf file with your ideas, no need to program anything (unless it will help you think these questions through). Reading section 3.2 of the Mehlhorn-Sanders book may be enlightening (you don't have to understand the proofs, just the gist of what they are saying).