Mercurial > Algorithms__Sedgewick
diff 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 |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/algs4-c++/src/Queue.cpp Fri May 29 21:13:32 2015 -0500 1.3 @@ -0,0 +1,159 @@ 1.4 +// g++ -D QUEUE_MAIN -std=c++0x Queue.cpp 1.5 +// g++ -D QUEUE_MAIN -std=c++11 Queue.cpp 1.6 + 1.7 + 1.8 +#include "Queue.hpp" 1.9 + 1.10 +#include <cassert> 1.11 +#include <cstddef> 1.12 + 1.13 +#include <iostream> 1.14 + 1.15 +template <typename T> 1.16 +Queue<T>::Queue( void ) : 1.17 + N (0), 1.18 + first (nullptr), 1.19 + last (nullptr) 1.20 + { 1.21 + } 1.22 + 1.23 +template <typename T> 1.24 +Queue<T>::~Queue( void ) { 1.25 + assert( N == 0 ); // Catch the potential memory leak. 1.26 + while ( first ) { 1.27 + Node *next = first->next; 1.28 + delete first; 1.29 + first = next; 1.30 + } 1.31 + } 1.32 + 1.33 +template <typename T> 1.34 +void Queue<T>::enqueue( T &item ) { 1.35 + Node * node = new Node(); 1.36 + node->item = item; 1.37 + node->next = nullptr; 1.38 + 1.39 + if ( last ) { 1.40 + last->next = node; 1.41 + last = node; 1.42 + } 1.43 + else { 1.44 + last = first = node; 1.45 + } 1.46 + 1.47 + N++; 1.48 + } 1.49 + 1.50 +template <typename T> 1.51 +T Queue<T>::dequeue( void ) { 1.52 + assert( N > 0 ); 1.53 + 1.54 + T item = first->item; 1.55 + 1.56 + Node *old = first; 1.57 + first = first->next; 1.58 + delete old; 1.59 + N--; 1.60 + 1.61 + if ( ! first ) 1.62 + last = nullptr; 1.63 + 1.64 + return item; 1.65 + } 1.66 + 1.67 +template <typename T> 1.68 +bool Queue<T>::is_empty( void ) { 1.69 + return N == 0; 1.70 + } 1.71 + 1.72 +template <typename T> 1.73 +size_t Queue<T>::size( void ) { 1.74 + return N; 1.75 + } 1.76 + 1.77 +template <typename T> 1.78 +typename Queue<T>::iterator Queue<T>::begin( void ) { 1.79 + return Queue<T>::iterator( first ); 1.80 + } 1.81 + 1.82 +template <typename T> 1.83 +typename Queue<T>::iterator Queue<T>::end( void ) { 1.84 + return Queue<T>::iterator( nullptr ); 1.85 + } 1.86 + 1.87 + 1.88 +//////////////////////////////////////////////////////////////////////////////// 1.89 + 1.90 +template <typename T> 1.91 +Queue<T>::iterator::iterator( Node *c ) : 1.92 + curr (c) 1.93 + { 1.94 + } 1.95 + 1.96 +template <typename T> 1.97 +typename Queue<T>::iterator & Queue<T>::iterator::operator++() { 1.98 + if ( this->curr != nullptr ) { 1.99 + this->curr = this->curr->next; 1.100 + } 1.101 + return *this; 1.102 + } 1.103 + 1.104 +template <typename T> 1.105 +typename Queue<T>::iterator Queue<T>::iterator::operator++( int ) { 1.106 + auto t = Queue<T>::iterator( *this ); 1.107 + 1.108 + if ( this->curr != nullptr ) { 1.109 + this->curr = this->curr->next; 1.110 + } 1.111 + return t; 1.112 + } 1.113 + 1.114 +template <typename T> 1.115 +T Queue<T>::iterator::operator*() { 1.116 + return this->curr->item; 1.117 + } 1.118 + 1.119 +template <typename T> 1.120 +bool Queue<T>::iterator::operator!=( typename Queue<T>::iterator other ) { 1.121 + return this->curr != other.curr; 1.122 + } 1.123 + 1.124 + 1.125 +//////////////////////////////////////////////////////////////////////////////// 1.126 + 1.127 +#ifdef QUEUE_MAIN 1.128 + 1.129 +#include <iostream> 1.130 + 1.131 +int main ( int argc, char **argv ) { 1.132 + 1.133 + Queue<long> queue; 1.134 + 1.135 + long i; 1.136 + while ( ! std::cin.eof() ) { 1.137 + std::cin >> i; 1.138 + if ( std::cin.good() ) 1.139 + if ( i >= 0 ) 1.140 + queue.enqueue(i); 1.141 + else 1.142 + queue.dequeue(); 1.143 + } 1.144 + 1.145 + std::cout << "Queue has " << queue.size() << " entries." << std::endl; 1.146 + 1.147 + for ( auto iter = queue.begin(); iter != queue.end(); ++iter ) { 1.148 + std::cout << *iter << std::endl; 1.149 + } 1.150 + 1.151 + std::cout << "Dequeuing entries..." << std::endl; 1.152 + 1.153 + while ( ! queue.is_empty() ) { 1.154 + i = queue.dequeue(); 1.155 + std::cout << i << std::endl; 1.156 + } 1.157 + 1.158 + std::cout << "Queue has " << queue.size() << " entries." << std::endl; 1.159 + 1.160 + } 1.161 + 1.162 +#endif