Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Queue.hpp @ 18:a149b424b4e2

find changesets by author, revision, files, or words in the commit message
Updated all template classes to have the implementaiton in the header file.
author Eris Caffee <discordia@eldalin.com>
date Sat, 20 Jun 2015 19:36:11 -0500
parents eb159ea69f33
children 028689700a47
line source
1 // Linked list based queue after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
2
3 #ifndef QUEUE_HPP
4 #define QUEUE_HPP
5
6 #include <cstddef>
7 #include <cassert>
8
9 template <typename T>
10 class Queue {
11
12 private:
13
14 ////////////////////////////////////
15 class Node {
16 public:
17 T item;
18 Node *next;
19 };
20
21 public:
22
23 ////////////////////////////////////
24 class iterator;
25 friend class iterator;
26 class iterator {
27
28 public:
29
30 iterator( Node *c );
31
32 iterator& operator++();
33 iterator operator++(int);
34
35 T operator*();
36 bool operator!=( typename Queue<T>::iterator );
37
38 private:
39
40 Node *curr;
41 };
42
43 ////////////////////////////////////
44
45 Queue( void );
46 ~Queue( void );
47
48 void enqueue( T &item );
49 T dequeue( void );
50
51 bool is_empty( void );
52 size_t size( void );
53
54 iterator begin( void );
55 iterator end( void );
56
57
58 private:
59
60 size_t N;
61 Node *first;
62 Node *last;
63
64 };
65
66
67 template <typename T>
68 Queue<T>::Queue( void ) :
69 N (0),
70 first (nullptr),
71 last (nullptr)
72 {
73 }
74
75 template <typename T>
76 Queue<T>::~Queue( void ) {
77 assert( N == 0 ); // Catch the potential memory leak.
78 while ( first ) {
79 Node *next = first->next;
80 delete first;
81 first = next;
82 }
83 }
84
85 template <typename T>
86 void Queue<T>::enqueue( T &item ) {
87 Node * node = new Node();
88 node->item = item;
89 node->next = nullptr;
90
91 if ( last ) {
92 last->next = node;
93 last = node;
94 }
95 else {
96 last = first = node;
97 }
98
99 N++;
100 }
101
102 template <typename T>
103 T Queue<T>::dequeue( void ) {
104 assert( N > 0 );
105
106 T item = first->item;
107
108 Node *old = first;
109 first = first->next;
110 delete old;
111 N--;
112
113 if ( ! first )
114 last = nullptr;
115
116 return item;
117 }
118
119 template <typename T>
120 bool Queue<T>::is_empty( void ) {
121 return N == 0;
122 }
123
124 template <typename T>
125 size_t Queue<T>::size( void ) {
126 return N;
127 }
128
129 template <typename T>
130 typename Queue<T>::iterator Queue<T>::begin( void ) {
131 return Queue<T>::iterator( first );
132 }
133
134 template <typename T>
135 typename Queue<T>::iterator Queue<T>::end( void ) {
136 return Queue<T>::iterator( nullptr );
137 }
138
139
140 ////////////////////////////////////////////////////////////////////////////////
141
142 template <typename T>
143 Queue<T>::iterator::iterator( Node *c ) :
144 curr (c)
145 {
146 }
147
148 template <typename T>
149 typename Queue<T>::iterator & Queue<T>::iterator::operator++() {
150 if ( this->curr != nullptr ) {
151 this->curr = this->curr->next;
152 }
153 return *this;
154 }
155
156 template <typename T>
157 typename Queue<T>::iterator Queue<T>::iterator::operator++( int ) {
158 auto t = Queue<T>::iterator( *this );
159
160 if ( this->curr != nullptr ) {
161 this->curr = this->curr->next;
162 }
163 return t;
164 }
165
166 template <typename T>
167 T Queue<T>::iterator::operator*() {
168 return this->curr->item;
169 }
170
171 template <typename T>
172 bool Queue<T>::iterator::operator!=( typename Queue<T>::iterator other ) {
173 return this->curr != other.curr;
174 }
175
176
177 #endif
178