Mercurial > Algorithms__Sedgewick
diff algs4-c++/src/ResizingArrayStack.cpp @ 3:ca59e5f5b29e
Initial, imcomplete, C++ version of ResizingArrayStack.
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Tue, 26 May 2015 18:18:16 -0500 |
parents | |
children | 310618f5e32a |
line diff
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