1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/algs4-c++/src/ResizingArrayStack.cpp	Tue May 26 18:18:16 2015 -0500
     1.3 @@ -0,0 +1,83 @@
     1.4 +// g++ -std=c++0x ResizingArrayStack.cpp
     1.5 +// g++ -std=c++11 ResizingArrayStack.cpp
     1.6 +
     1.7 +
     1.8 +#include "ResizingArrayStack.hpp"
     1.9 +
    1.10 +#include <cassert>
    1.11 +#include <cstddef>
    1.12 +
    1.13 +#include <iostream>
    1.14 +
    1.15 +template <typename T> ResizingArrayStack<T>::ResizingArrayStack( void ) :
    1.16 +    N (0),
    1.17 +    max(1) {
    1.18 +    data = new T[1];
    1.19 +    }
    1.20 +    
    1.21 +template <typename T> ResizingArrayStack<T>::~ResizingArrayStack( void ) {
    1.22 +    assert( N == 0 );  // Catch the potential memory leak.
    1.23 +    if ( data )
    1.24 +        delete data;
    1.25 +    }
    1.26 +
    1.27 +template <typename T> void ResizingArrayStack<T>::push( T &item ) {
    1.28 +    if ( max == N )
    1.29 +        resize( 2 * max );
    1.30 +    data[N++] = item;
    1.31 +    }
    1.32 +
    1.33 +template <typename T> T ResizingArrayStack<T>::pop( void ) {
    1.34 +    assert( N > 0 );
    1.35 +    T item = data[N-1];
    1.36 +    data[N-1] = NULL;
    1.37 +    N--;
    1.38 +
    1.39 +    if ( N <= max/4 )
    1.40 +        resize( max/2 );
    1.41 +
    1.42 +    return item;
    1.43 +    }
    1.44 +
    1.45 +template <typename T> bool ResizingArrayStack<T>::is_empty( void ) {
    1.46 +    return N == 0;
    1.47 +    }
    1.48 +
    1.49 +template <typename T> size_t ResizingArrayStack<T>::size( void ) {
    1.50 +    return N;
    1.51 +    }
    1.52 +
    1.53 +template <typename T> void ResizingArrayStack<T>::resize( size_t new_max ) {
    1.54 +    T *new_data = new T[new_max];
    1.55 +    for ( size_t i = 0; i < N; ++i )
    1.56 +        new_data[i] = data[i];
    1.57 +    T *old_data = data;
    1.58 +    data = new_data;
    1.59 +    delete old_data;
    1.60 +    max = new_max;
    1.61 +    }
    1.62 +
    1.63 +#ifdef RESIZINGARRAYSTACK_MAIN
    1.64 +
    1.65 +#include <iostream>
    1.66 +
    1.67 +int main ( int argc, char **argv ) {
    1.68 +
    1.69 +    ResizingArrayStack<long> stack;
    1.70 +
    1.71 +    long i;
    1.72 +    while ( ! std::cin.eof() ) {
    1.73 +        std::cin >> i;
    1.74 +        if ( std::cin.good() ) 
    1.75 +            stack.push(i);
    1.76 +        }
    1.77 +
    1.78 +    std::cout << "Stack has " << stack.size() << " entries." << std::endl;
    1.79 +
    1.80 +    while ( ! stack.is_empty() ) {
    1.81 +        i = stack.pop();
    1.82 +        std::cout << i << std::endl;
    1.83 +        }
    1.84 +    }
    1.85 +
    1.86 +#endif