Mercurial > Algorithms__Sedgewick
changeset 3:ca59e5f5b29e
Initial, imcomplete, C++ version of ResizingArrayStack.
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Tue, 26 May 2015 18:18:16 -0500 |
parents | d1e563e7873f |
children | 310618f5e32a |
files | .hgignore algs4-c++/src/ResizingArrayStack.cpp algs4-c++/src/ResizingArrayStack.hpp |
diffstat | 3 files changed, 121 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- a/.hgignore Sat May 23 20:44:30 2015 -0500 1.2 +++ b/.hgignore Tue May 26 18:18:16 2015 -0500 1.3 @@ -2,3 +2,4 @@ 1.4 algs4/algs4-code/.* 1.5 .*~$ 1.6 .*\.class$ 1.7 +a\.out$
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/algs4-c++/src/ResizingArrayStack.cpp Tue May 26 18:18:16 2015 -0500 2.3 @@ -0,0 +1,83 @@ 2.4 +// g++ -std=c++0x ResizingArrayStack.cpp 2.5 +// g++ -std=c++11 ResizingArrayStack.cpp 2.6 + 2.7 + 2.8 +#include "ResizingArrayStack.hpp" 2.9 + 2.10 +#include <cassert> 2.11 +#include <cstddef> 2.12 + 2.13 +#include <iostream> 2.14 + 2.15 +template <typename T> ResizingArrayStack<T>::ResizingArrayStack( void ) : 2.16 + N (0), 2.17 + max(1) { 2.18 + data = new T[1]; 2.19 + } 2.20 + 2.21 +template <typename T> ResizingArrayStack<T>::~ResizingArrayStack( void ) { 2.22 + assert( N == 0 ); // Catch the potential memory leak. 2.23 + if ( data ) 2.24 + delete data; 2.25 + } 2.26 + 2.27 +template <typename T> void ResizingArrayStack<T>::push( T &item ) { 2.28 + if ( max == N ) 2.29 + resize( 2 * max ); 2.30 + data[N++] = item; 2.31 + } 2.32 + 2.33 +template <typename T> T ResizingArrayStack<T>::pop( void ) { 2.34 + assert( N > 0 ); 2.35 + T item = data[N-1]; 2.36 + data[N-1] = NULL; 2.37 + N--; 2.38 + 2.39 + if ( N <= max/4 ) 2.40 + resize( max/2 ); 2.41 + 2.42 + return item; 2.43 + } 2.44 + 2.45 +template <typename T> bool ResizingArrayStack<T>::is_empty( void ) { 2.46 + return N == 0; 2.47 + } 2.48 + 2.49 +template <typename T> size_t ResizingArrayStack<T>::size( void ) { 2.50 + return N; 2.51 + } 2.52 + 2.53 +template <typename T> void ResizingArrayStack<T>::resize( size_t new_max ) { 2.54 + T *new_data = new T[new_max]; 2.55 + for ( size_t i = 0; i < N; ++i ) 2.56 + new_data[i] = data[i]; 2.57 + T *old_data = data; 2.58 + data = new_data; 2.59 + delete old_data; 2.60 + max = new_max; 2.61 + } 2.62 + 2.63 +#ifdef RESIZINGARRAYSTACK_MAIN 2.64 + 2.65 +#include <iostream> 2.66 + 2.67 +int main ( int argc, char **argv ) { 2.68 + 2.69 + ResizingArrayStack<long> stack; 2.70 + 2.71 + long i; 2.72 + while ( ! std::cin.eof() ) { 2.73 + std::cin >> i; 2.74 + if ( std::cin.good() ) 2.75 + stack.push(i); 2.76 + } 2.77 + 2.78 + std::cout << "Stack has " << stack.size() << " entries." << std::endl; 2.79 + 2.80 + while ( ! stack.is_empty() ) { 2.81 + i = stack.pop(); 2.82 + std::cout << i << std::endl; 2.83 + } 2.84 + } 2.85 + 2.86 +#endif
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 3.2 +++ b/algs4-c++/src/ResizingArrayStack.hpp Tue May 26 18:18:16 2015 -0500 3.3 @@ -0,0 +1,37 @@ 3.4 +#ifndef RESIZINGARRAYSTACK_HPP 3.5 +#define RESIZINGARRAYSTACK_HPP 3.6 + 3.7 +#include <cstddef> 3.8 + 3.9 +template <typename T> 3.10 +class ResizingArrayStack { 3.11 + 3.12 +public: 3.13 + 3.14 + ResizingArrayStack( void ); 3.15 + ~ResizingArrayStack( void ); 3.16 + 3.17 + void push( T &item ); 3.18 + T pop( void ); 3.19 + 3.20 + bool is_empty( void ); 3.21 + size_t size( void ); 3.22 + 3.23 + // class iterator; 3.24 + // friend class iterator; 3.25 + // class iterator { 3.26 + // }; 3.27 + 3.28 +private: 3.29 + 3.30 + size_t N; 3.31 + size_t max; 3.32 + T *data; 3.33 + 3.34 + void resize( size_t new_max ); 3.35 + }; 3.36 + 3.37 + 3.38 + 3.39 +#endif 3.40 +