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