Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Stack.cpp @ 6:438f5608900e

find changesets by author, revision, files, or words in the commit message
Linked list based Stack class.
author Eris Caffee <discordia@eldalin.com>
date Fri, 29 May 2015 20:52:18 -0500
parents
children 8af1a61be7c1
line source
1 // g++ -D STACK_MAIN -std=c++0x Stack.cpp
2 // g++ -D STACK_MAIN -std=c++11 Stack.cpp
3
4
5 #include "Stack.hpp"
6
7 #include <cassert>
8 #include <cstddef>
9
10 #include <iostream>
11
12 template <typename T>
13 Stack<T>::Stack( void ) :
14 N (0),
15 list (nullptr)
16 {
17 }
18
19 template <typename T>
20 Stack<T>::~Stack( void ) {
21 assert( N == 0 ); // Catch the potential memory leak.
22 while ( list ) {
23 Node * next = list->next;
24 delete list;
25 list = next;
26 }
27 }
28
29 template <typename T>
30 void Stack<T>::push( T &item ) {
31 Node * node = new Node();
32 node->item = item;
33 node->next = list;
34 list = node;
35 N++;
36 }
37
38 template <typename T>
39 T Stack<T>::pop( void ) {
40 assert( N > 0 );
41
42 T item = list->item;
43
44 Node *old = list;
45 list = list->next;
46 delete old;
47 N--;
48
49 return item;
50 }
51
52 template <typename T>
53 bool Stack<T>::is_empty( void ) {
54 return N == 0;
55 }
56
57 template <typename T>
58 size_t Stack<T>::size( void ) {
59 return N;
60 }
61
62 template <typename T>
63 typename Stack<T>::iterator Stack<T>::begin( void ) {
64 return Stack<T>::iterator( list );
65 }
66
67 template <typename T>
68 typename Stack<T>::iterator Stack<T>::end( void ) {
69 return Stack<T>::iterator( nullptr );
70 }
71
72
73 ////////////////////////////////////////////////////////////////////////////////
74
75 template <typename T>
76 Stack<T>::iterator::iterator( Node *c ) :
77 curr (c)
78 {
79 }
80
81 template <typename T>
82 typename Stack<T>::iterator & Stack<T>::iterator::operator++() {
83 if ( this->curr != nullptr ) {
84 this->curr = this->curr->next;
85 }
86 return *this;
87 }
88
89 template <typename T>
90 typename Stack<T>::iterator Stack<T>::iterator::operator++( int ) {
91 auto t = Stack<T>::iterator( *this );
92
93 if ( this->curr != nullptr ) {
94 this->curr = this->curr->next;
95 }
96 return t;
97 }
98
99 template <typename T>
100 T Stack<T>::iterator::operator*() {
101 return this->curr->item;
102 }
103
104 template <typename T>
105 bool Stack<T>::iterator::operator!=( typename Stack<T>::iterator other ) {
106 return this->curr != other.curr;
107 }
108
109
110 ////////////////////////////////////////////////////////////////////////////////
111
112 #ifdef STACK_MAIN
113
114 #include <iostream>
115
116 int main ( int argc, char **argv ) {
117
118 Stack<long> stack;
119
120 long i;
121 while ( ! std::cin.eof() ) {
122 std::cin >> i;
123 if ( std::cin.good() )
124 stack.push(i);
125 }
126
127 std::cout << "Stack has " << stack.size() << " entries." << std::endl;
128
129 for ( auto iter = stack.begin(); iter != stack.end(); ++iter ) {
130 std::cout << *iter << std::endl;
131 }
132
133 std::cout << "Popping entries..." << std::endl;
134
135 while ( ! stack.is_empty() ) {
136 i = stack.pop();
137 std::cout << i << std::endl;
138 }
139
140 std::cout << "Stack has " << stack.size() << " entries." << std::endl;
141
142 }
143
144 #endif