Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Queue.cpp @ 8:b02533162b6e

find changesets by author, revision, files, or words in the commit message
Linked list based Queue class.
author Eris Caffee <discordia@eldalin.com>
date Fri, 29 May 2015 21:13:32 -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