C++ In Action

Exercises

See the solutions

1. Add a private Shrink method to the dynamic stack. Let Pop call it when _top reaches some low water mark. Make sure the stack doesn’t have a size at which alternating Pushes and Pops lead to alternating allocations and deallocations.
2. Create a 2-deep stack of strings (char *). It’s a stack that "remembers" only the last and the one before last strings. When a new string is pushed, the "before last" string is deleted, the "last" string takes its place and the new one becomes "last." Pop returns the last string; it also moves up the "before last" to the "last" position one and stores zero in its place. In other words, the third Pop in a row will always return a zero pointer.
3. Create a queue of integers with the FIFO (First In First Out) protocol. Use a linked list to implement it.
4. Create a sequencer for a linked list. Create another sequencer that keeps track of both, the current and the previous item. Implement method Unlink on such a sequencer. It should remove the current item from the list that is being iterated. Test for special cases (remove first, remove last, one element list, etc.).
5. Create a doubly linked list item, DLink, with the _pNext as well as _pPrev pointers. Implement the Unlink method of the DLink object. Create a FIFO queue that uses a circular doubly linked list; that is, the last element points at the first element and the first element points back at the last element. Always create a new DLink with both links closed on itself. The pointer to itself can be accessed through the keyword this. For instance _pNext = this; will point _pNext at the current DLink.

   

   Figure 14. A circular doubly linked list.

6. Design and implement a sequencer for the hash table. It should go through all the entries in the array and follow all the non-empty linked lists.
7. Using the hash table sequencer from the previous problem, design and implement new StringTable that uses a dynamic hash table that grows by allocating a larger array, iterates through the old hash table and re-hashes each element into the new array. Notice that the new array’s hash function will differ from the old one (the division modulo size will use a different size).

Next: Polymorphism