Dynamic Stack
 

Dynamic Stack

Dynamic arrays

We will now modify the contract of our stack. There will no longer be a strict limit on how many integers can be pushed. We’ll be able to keep pushing until we run out of memory.

However, we would like our implementation not to be a memory hog, at least not when it’s not necessary. So every time we run out of space in the stack, we’ll just double its size. Obviously, we won’t need the method IsFull. Otherwise the interface will be the same as that of our ordinary stack.

Here’s how our new stack works: There's a private helper function Grow that's used internally to double the stack size when necessary. We store the current capacity of the stack in a private variable _capacity. For the purpose of testing we'll set the initial capacity of the stack to one, so that we'll be able to see the stack grow almost immediately.


Download!
source 
const int initStack = 1;

class IStack
{
public:
      IStack ();
      ~IStack ();
      void Push ( int i );
      int  Pop ();
      int  Top () const;
      bool IsEmpty () const;
private:
      void Grow ();

      int * _arr;
      int   _capacity; // size of the array
      int   _top;
};

Notice that _arr is declared as a pointer rather than an array. A dynamically allocated array has to be declared as a pointer.

We allocate the initial array in the constructor of IStack and we delete the memory in the destructor. 
IStack::IStack ()
      : _top (0), _capacity (initStack)
{
      _arr = new int [initStack]; // allocate memory
}

IStack::~IStack ()
{
      delete []_arr; // free memory
}

This is a new kind of relationships between objects. Not only can we say that IStack has access to the array, we can say that IStack owns the array. The owns-a relationship is expressed through a pointer. Object A owns object B if object A is responsible for object B’s deallocation. We’ll talk more about it when we discuss resource management.

owns-a relationship

Fig. The owns-a relationship between objects.

IStack acquires the memory for the array in its constructor and deallocates it in its destructor. In a moment we’ll see that the method Grow does some reallocation of its own.

So what happens when we Push an integer and there is no space left in the array? We call the Grow method and then complete the push. 
void IStack::Push (int i)
{
      assert (_top <= _capacity);
      if (_top == _capacity)
            Grow ();
      _arr [_top] = i;
      ++_top;
}

Let’s see what Grow does. It has to go through the following steps:

  • Allocate new array of twice the size of the current array
  • Copy all entries from the old array into the first half of the new array
  • Double the _capacity variable
  • Delete the old array
  • Set the pointer _arr to point to the newly allocated array.
void IStack::Grow ()
{
      cout << "Doubling stack from " << _capacity << ".\n";
      // allocate new array
      int * arrNew = new int [2 * _capacity];
      // copy all entries
      for (int i = 0; i < _capacity; ++i)
            arrNew [i] = _arr [i];
      _capacity = 2 * _capacity;
      // free old memory
      delete []_arr;
      // substitute new array for old array
      _arr = arrNew;
}

The statement 
_arr = arrNew;

is a pointer assignment. We are changing the pointer _arr to point into the new location--the same location arrNew is pointing at. This is the one operation that we cannot do with references. Notice: we are not changing the contents of the location. That would be done in the statement 
*_arr = *arrNew;

or its equivalent 
_arr [0] = arrNew [0];

We are changing the pointer _arr itself. 
_arr = arrNew;

For completeness, here are the implementations of the rest of the methods. Notice that although _arr is a pointer, it is accessed like an array. 
int IStack::Pop ()
{
      // Do not Pop an empty stack
      assert (_top > 0);
      --_top;
      return _arr [_top];
}

int IStack::Top () const
{
      // Don't call Top on an empty stack
      assert (_top > 0);
      return _arr [_top - 1];
}

bool IStack::IsEmpty () const
{
      assert (_top >= 0);
      return _top == 0;
}

And here’s a simple test program that forces the stack to grow a few times. Notice that we never shrink the stack. This is called a high water mark type of the algorithm. It would be easy though to add the Shrink method called by Pop every time _top gets much below _size/2. 
int main ()
{
      IStack stack;
      for (int i = 0; i < 5; ++i)
      {
            cout << "Push " << i << endl;
            stack.Push (i);
      }
      for (int j = 0; j < 5; ++j)
      {
            cout << "Pop " << stack.Pop () << endl;
      }
}