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