Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Steque.cpp @ 11:846aeab17939

find changesets by author, revision, files, or words in the commit message
Added Steque (exercise 1.3.32)
author Eris Caffee <discordia@eldalin.com>
date Wed, 10 Jun 2015 13:21:26 -0500
parents
children a149b424b4e2
line source
1 // g++ -D STEQUE_MAIN -std=c++0x Steque.cpp
2 // g++ -D STEQUE_MAIN -std=c++11 Steque.cpp
3
4
5 #include "Steque.hpp"
6
7 #include <cassert>
8 #include <cstddef>
9
10 #include <iostream>
11
12 template <typename T>
13 Steque<T>::Steque( void ) :
14 N (0),
15 list (nullptr)
16 {
17 }
18
19 template <typename T>
20 Steque<T>::~Steque( 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 Steque<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 Steque<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 void Steque<T>::enqueue( T &item ) {
54 Node *curr = list;
55
56 Node *node = new Node();
57 node->item = item;
58 node->next = nullptr;
59
60 if ( ! curr ) {
61 list = node;
62 N++;
63 return;
64 }
65
66 while ( curr->next ) {
67 curr = curr->next;
68 }
69
70 curr->next = node;
71 N++;
72
73 return;
74 }
75
76 template <typename T>
77 bool Steque<T>::is_empty( void ) {
78 return N == 0;
79 }
80
81 template <typename T>
82 size_t Steque<T>::size( void ) {
83 return N;
84 }
85
86 template <typename T>
87 typename Steque<T>::iterator Steque<T>::begin( void ) {
88 return Steque<T>::iterator( list );
89 }
90
91 template <typename T>
92 typename Steque<T>::iterator Steque<T>::end( void ) {
93 return Steque<T>::iterator( nullptr );
94 }
95
96
97 ////////////////////////////////////////////////////////////////////////////////
98
99 template <typename T>
100 Steque<T>::iterator::iterator( Node *c ) :
101 curr (c)
102 {
103 }
104
105 template <typename T>
106 typename Steque<T>::iterator & Steque<T>::iterator::operator++() {
107 if ( this->curr != nullptr ) {
108 this->curr = this->curr->next;
109 }
110 return *this;
111 }
112
113 template <typename T>
114 typename Steque<T>::iterator Steque<T>::iterator::operator++( int ) {
115 auto t = Steque<T>::iterator( *this );
116
117 if ( this->curr != nullptr ) {
118 this->curr = this->curr->next;
119 }
120 return t;
121 }
122
123 template <typename T>
124 T Steque<T>::iterator::operator*() {
125 return this->curr->item;
126 }
127
128 template <typename T>
129 bool Steque<T>::iterator::operator!=( typename Steque<T>::iterator other ) {
130 return this->curr != other.curr;
131 }
132
133 ////////////////////////////////////////////////////////////////////////////////
134
135
136
137 #ifdef STEQUE_MAIN
138
139 #include <iostream>
140
141 int main ( int argc, char **argv ) {
142
143 Steque<long> steque;
144 bool push_it = true;
145
146 long i;
147 while ( ! std::cin.eof() ) {
148 std::cin >> i;
149 if ( std::cin.good() ) {
150 if ( push_it ) {
151 steque.push( i );
152 push_it = false;
153 }
154 else {
155 steque.enqueue( i );
156 push_it = true;
157 }
158 }
159 }
160
161 std::cout << "Steque has " << steque.size() << " entries." << std::endl;
162
163 for ( auto iter = steque.begin(); iter != steque.end(); ++iter ) {
164 std::cout << *iter << std::endl;
165 }
166
167 std::cout << "Popping entries..." << std::endl;
168
169 while ( ! steque.is_empty() ) {
170 i = steque.pop();
171 std::cout << i << std::endl;
172 }
173
174 std::cout << "Steque has " << steque.size() << " entries." << std::endl;
175
176 }
177
178 #endif