Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Queue.cpp @ 15:63df3e6590e2

find changesets by author, revision, files, or words in the commit message
Bag and RandomBag (1.3.34) classes. There are not really robust enough to use as they will leak memory on destruction if you use them to store dynamically allocated objects.
author Eris Caffee <discordia@eldalin.com>
date Thu, 11 Jun 2015 16:30:14 -0500
parents
children eb159ea69f33
line source
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