Exercise Solutions
 

Exercise Solutions

  1. You don’t want to shrink the stack down to _top, because then the next push would have to grow it again. A reasonable policy is for instance to shrink the capacity of the stack to twice the current _top. We choose to shrink only when _top goes down to 1/3 of the current capacity. 
    int IStack::Pop ()
{
    assert (_top > 0);
    --_top;
    if (_top >= 1 && 3 * _top < _capacity)
        Shrink ();
    return _arr [_top];
}

void IStack::Shrink ()
{
    std::cout << "Shrinking stack from "
        << _capacity << " to " << 2 * _top << ".\n";
    assert (2 * _top < _capacity);
    // allocate new array
    int * arrNew = new int [2 * _top];
    // copy all entries
    for (int i = 0; i < _top + 1; ++i)
        arrNew [i] = _arr [i];
    _capacity = 2 * _top;
    // free old memory
    delete []_arr;
    // substitute new array for old array
    _arr = arrNew;
}
  2.   
    Stack2::Stack2 ()
    : _last (0), _previous (0)
{}

void Stack2::Push (char const * str)
{
    _previous = _last;
    _last = str;
}

void Stack2::Pop ()
{
    _last = _previous;
    _previous = 0;
}

char const * Stack2::Top () const
{
    return _last;
}
  3. The trick is to keep two pointers: one pointing at the head of the list and the other at its tail. When removing elements, we use the head pointer. We add new elements to the tail. As usual, we are really careful about boundary cases--the queue starting empty and becoming empty. 
    void Queue::Put (int i)
{
    Link * newLink = new Link (i);
    if (_tail == 0)
    {
        _head = newLink;
    }
    else
    {
        _tail->SetNext (newLink);
    }
    _tail = newLink;
}

int Queue::Get ()
{
    assert (_head != 0);
    int i = _head->Value ();
    Link * tmp = _head;
    _head = _head->Next ();
    // don't delete recursively!
    tmp->SetNext (0); 
    delete tmp;
    if (_head == 0)
        _tail = 0;
    return i;
}
  4.   
    class UnlinkSeq
{
public:
    UnlinkSeq (List & list)
        : _list (list),
          _cur (list._pHead),
          _prev (0)
    {}
    bool AtEnd () const { return _cur == 0; }
    void Advance ()
    {
        _prev = _cur;
        _cur = _cur->Next ();
    }
    int Id () const { return _cur->Id (); }
    void Unlink ();
private:
    List & _list;
    Link * _cur;
    Link * _prev;
};

void UnlinkSeq::Unlink ()
{
    assert (_cur != 0);
    if (_prev == 0)
    {
        assert (_cur == _list._pHead);
        _list._pHead = _cur->Next ();
    }
    else
    {
        _prev->SetNext (_cur->Next ());
    }
    delete _cur;
    _cur = 0;
}

    Notice that after calling Unlink the sequencer is no longer valid. You might try to chose an implementation which doesn't invalidate it, but there is a bigger problem. When one sequencer modifies the list, other sequencers that pointed to the same element will become invalid no matter what. So it's better to assume that any modification to a list may invalidate all sequencers, including the current one. This convention was also adopted by the C++ Standard Library.

  5. It helps to draw diagrams to see how the pointer manipulations work in these methods. 
    void DLink::Unlink ()
{
    assert (_pNext != 0);
    assert (_pPrev != 0);
    _pNext->SetPrev (_pPrev);
    _pPrev->SetNext (_pNext);
    _pPrev = this;
    _pNext = this;
}

void List::Put (int id)
{
    DLink * pLink = new DLink (id);
    if (_pHead == 0)
        _pHead = pLink;
    else
    {
        pLink->SetNext (_pHead);
        pLink->SetPrev (_pHead->Prev ());
        _pHead->Prev ()->SetNext (pLink);
        _pHead->SetPrev (pLink);
        _pHead = pLink;
    }
}

int List::Get ()
{
    assert (_pHead != 0);
    DLink * pLink = _pHead->Prev ();
    if (pLink == _pHead) // last one
        _pHead = 0;
    pLink->Unlink ();
    int result = pLink->Id ();
    delete pLink;
    return result;
}
  6. Notice the implicit conversion from an array of Lists to a pointer to List in the constructor of HSeq. This is an example of array/pointer equivalence. 
    class HSeq
{
public:
    HSeq (HTable const & htab)
        : _aList (htab._aList),
          _idx (-1),
          _link (0)
    {
        NextList ();
    }
    bool AtEnd () const
        { return _idx == sizeHTable && _link == 0; }
    void Advance ();
    int Get () { return _link->Id (); }
private:
    void NextList ();
    
    List const * _aList;
    int          _idx;
    Link const * _link;
};
    The Advance method tries to follow the current link, but if it finds the end of the current list, it searches for the next non-empty list. 
    void HSeq::Advance ()
{
    _link = _link->Next ();
    if (_link == 0)
        NextList ();
}

void HSeq::NextList ()
{
    assert (_link == 0);
    do
    {
        ++_idx;
    } while (_aList [_idx].IsEmpty ());

    if (_idx < sizeHTable)
        _link = _aList [_idx].GetHead ();
    else
        _link = 0;
}