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