Mercurial > Algorithms__Sedgewick
annotate 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 |
| rev | line source |
|---|---|
| discordia@3 | 1 // g++ -std=c++0x ResizingArrayStack.cpp |
| discordia@3 | 2 // g++ -std=c++11 ResizingArrayStack.cpp |
| discordia@3 | 3 |
| discordia@3 | 4 |
| discordia@3 | 5 #include "ResizingArrayStack.hpp" |
| discordia@3 | 6 |
| discordia@3 | 7 #include <cassert> |
| discordia@3 | 8 #include <cstddef> |
| discordia@3 | 9 |
| discordia@3 | 10 #include <iostream> |
| discordia@3 | 11 |
| discordia@3 | 12 template <typename T> ResizingArrayStack<T>::ResizingArrayStack( void ) : |
| discordia@3 | 13 N (0), |
| discordia@3 | 14 max(1) { |
| discordia@3 | 15 data = new T[1]; |
| discordia@3 | 16 } |
| discordia@3 | 17 |
| discordia@3 | 18 template <typename T> ResizingArrayStack<T>::~ResizingArrayStack( void ) { |
| discordia@3 | 19 assert( N == 0 ); // Catch the potential memory leak. |
| discordia@3 | 20 if ( data ) |
| discordia@3 | 21 delete data; |
| discordia@3 | 22 } |
| discordia@3 | 23 |
| discordia@3 | 24 template <typename T> void ResizingArrayStack<T>::push( T &item ) { |
| discordia@3 | 25 if ( max == N ) |
| discordia@3 | 26 resize( 2 * max ); |
| discordia@3 | 27 data[N++] = item; |
| discordia@3 | 28 } |
| discordia@3 | 29 |
| discordia@3 | 30 template <typename T> T ResizingArrayStack<T>::pop( void ) { |
| discordia@3 | 31 assert( N > 0 ); |
| discordia@3 | 32 T item = data[N-1]; |
| discordia@3 | 33 data[N-1] = NULL; |
| discordia@3 | 34 N--; |
| discordia@3 | 35 |
| discordia@3 | 36 if ( N <= max/4 ) |
| discordia@3 | 37 resize( max/2 ); |
| discordia@3 | 38 |
| discordia@3 | 39 return item; |
| discordia@3 | 40 } |
| discordia@3 | 41 |
| discordia@3 | 42 template <typename T> bool ResizingArrayStack<T>::is_empty( void ) { |
| discordia@3 | 43 return N == 0; |
| discordia@3 | 44 } |
| discordia@3 | 45 |
| discordia@3 | 46 template <typename T> size_t ResizingArrayStack<T>::size( void ) { |
| discordia@3 | 47 return N; |
| discordia@3 | 48 } |
| discordia@3 | 49 |
| discordia@3 | 50 template <typename T> void ResizingArrayStack<T>::resize( size_t new_max ) { |
| discordia@3 | 51 T *new_data = new T[new_max]; |
| discordia@3 | 52 for ( size_t i = 0; i < N; ++i ) |
| discordia@3 | 53 new_data[i] = data[i]; |
| discordia@3 | 54 T *old_data = data; |
| discordia@3 | 55 data = new_data; |
| discordia@3 | 56 delete old_data; |
| discordia@3 | 57 max = new_max; |
| discordia@3 | 58 } |
| discordia@3 | 59 |
| discordia@3 | 60 #ifdef RESIZINGARRAYSTACK_MAIN |
| discordia@3 | 61 |
| discordia@3 | 62 #include <iostream> |
| discordia@3 | 63 |
| discordia@3 | 64 int main ( int argc, char **argv ) { |
| discordia@3 | 65 |
| discordia@3 | 66 ResizingArrayStack<long> stack; |
| discordia@3 | 67 |
| discordia@3 | 68 long i; |
| discordia@3 | 69 while ( ! std::cin.eof() ) { |
| discordia@3 | 70 std::cin >> i; |
| discordia@3 | 71 if ( std::cin.good() ) |
| discordia@3 | 72 stack.push(i); |
| discordia@3 | 73 } |
| discordia@3 | 74 |
| discordia@3 | 75 std::cout << "Stack has " << stack.size() << " entries." << std::endl; |
| discordia@3 | 76 |
| discordia@3 | 77 while ( ! stack.is_empty() ) { |
| discordia@3 | 78 i = stack.pop(); |
| discordia@3 | 79 std::cout << i << std::endl; |
| discordia@3 | 80 } |
| discordia@3 | 81 } |
| discordia@3 | 82 |
| discordia@3 | 83 #endif |