1.1 --- a/algs4-c++/src/Queue.cpp	Thu Jun 11 16:30:14 2015 -0500
     1.2 +++ b/algs4-c++/src/Queue.cpp	Fri Jun 19 18:17:46 2015 -0500
     1.3 @@ -1,129 +1,9 @@
     1.4 -// g++ -D QUEUE_MAIN -std=c++0x Queue.cpp
     1.5 -// g++ -D QUEUE_MAIN -std=c++11 Queue.cpp
     1.6 +// g++ -std=c++11 Queue.cpp
     1.7  
     1.8  
     1.9 -#include "Queue.hpp"
    1.10 -
    1.11 -#include <cassert>
    1.12 -#include <cstddef>
    1.13 -
    1.14  #include <iostream>
    1.15  
    1.16 -template <typename T>
    1.17 -Queue<T>::Queue( void ) :
    1.18 -    N (0),
    1.19 -    first (nullptr),
    1.20 -    last (nullptr)
    1.21 -    {
    1.22 -    }
    1.23 -    
    1.24 -template <typename T>
    1.25 -Queue<T>::~Queue( void ) {
    1.26 -    assert( N == 0 );  // Catch the potential memory leak.
    1.27 -    while ( first ) {
    1.28 -        Node *next = first->next;
    1.29 -        delete first;
    1.30 -        first = next;
    1.31 -        }
    1.32 -    }
    1.33 -
    1.34 -template <typename T>
    1.35 -void Queue<T>::enqueue( T &item ) {
    1.36 -    Node * node = new Node();
    1.37 -    node->item = item;
    1.38 -    node->next = nullptr;
    1.39 -
    1.40 -    if ( last ) {
    1.41 -        last->next = node;
    1.42 -        last = node;
    1.43 -        }
    1.44 -    else {
    1.45 -        last = first = node;
    1.46 -        }
    1.47 -
    1.48 -    N++;
    1.49 -    }
    1.50 -
    1.51 -template <typename T>
    1.52 -T Queue<T>::dequeue( void ) {
    1.53 -    assert( N > 0 );
    1.54 -
    1.55 -    T item = first->item;
    1.56 -
    1.57 -    Node *old = first;
    1.58 -    first = first->next;
    1.59 -    delete old;
    1.60 -    N--;
    1.61 -
    1.62 -    if ( ! first )
    1.63 -        last = nullptr;
    1.64 -
    1.65 -    return item;
    1.66 -    }
    1.67 -
    1.68 -template <typename T>
    1.69 -bool Queue<T>::is_empty( void ) {
    1.70 -    return N == 0;
    1.71 -    }
    1.72 -
    1.73 -template <typename T>
    1.74 -size_t Queue<T>::size( void ) {
    1.75 -    return N;
    1.76 -    }
    1.77 -
    1.78 -template <typename T>
    1.79 -typename Queue<T>::iterator Queue<T>::begin( void ) {
    1.80 -    return Queue<T>::iterator( first );
    1.81 -    }
    1.82 -
    1.83 -template <typename T>
    1.84 -typename Queue<T>::iterator Queue<T>::end( void ) {
    1.85 -    return Queue<T>::iterator( nullptr );
    1.86 -    }
    1.87 -
    1.88 -
    1.89 -////////////////////////////////////////////////////////////////////////////////
    1.90 -
    1.91 -template <typename T>
    1.92 -Queue<T>::iterator::iterator( Node *c ) :
    1.93 -    curr (c)
    1.94 -    {
    1.95 -    }
    1.96 -
    1.97 -template <typename T>
    1.98 -typename Queue<T>::iterator & Queue<T>::iterator::operator++() {
    1.99 -    if ( this->curr != nullptr ) {
   1.100 -        this->curr = this->curr->next;
   1.101 -        }
   1.102 -    return *this;
   1.103 -    }
   1.104 -
   1.105 -template <typename T>
   1.106 -typename Queue<T>::iterator Queue<T>::iterator::operator++( int ) {
   1.107 -    auto t = Queue<T>::iterator( *this );
   1.108 -
   1.109 -    if ( this->curr != nullptr ) {
   1.110 -        this->curr = this->curr->next;
   1.111 -        }
   1.112 -    return t;
   1.113 -    }
   1.114 -
   1.115 -template <typename T>
   1.116 -T Queue<T>::iterator::operator*() {
   1.117 -    return this->curr->item;
   1.118 -    }
   1.119 -
   1.120 -template <typename T>
   1.121 -bool Queue<T>::iterator::operator!=( typename Queue<T>::iterator other ) {
   1.122 -    return this->curr != other.curr;
   1.123 -    }
   1.124 -
   1.125 -
   1.126 -////////////////////////////////////////////////////////////////////////////////
   1.127 -
   1.128 -#ifdef QUEUE_MAIN
   1.129 -
   1.130 -#include <iostream>
   1.131 +#include "Queue.hpp"
   1.132  
   1.133  int main ( int argc, char **argv ) {
   1.134  
   1.135 @@ -156,4 +36,3 @@
   1.136  
   1.137      }
   1.138  
   1.139 -#endif

     2.1 --- a/algs4-c++/src/Queue.hpp	Thu Jun 11 16:30:14 2015 -0500
     2.2 +++ b/algs4-c++/src/Queue.hpp	Fri Jun 19 18:17:46 2015 -0500
     2.3 @@ -1,9 +1,12 @@
     2.4 +// Linked list based queue after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
     2.5 +
     2.6  #ifndef QUEUE_HPP
     2.7  #define QUEUE_HPP
     2.8  
     2.9  #include <cstddef>
    2.10 +#include <cassert>
    2.11 +#include <iostream>
    2.12  
    2.13 -// Linked list based queue after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
    2.14  
    2.15  template <typename T>
    2.16  class Queue {
    2.17 @@ -63,6 +66,115 @@
    2.18      };
    2.19  
    2.20  
    2.21 +template <typename T>
    2.22 +Queue<T>::Queue( void ) :
    2.23 +    N (0),
    2.24 +    first (nullptr),
    2.25 +    last (nullptr)
    2.26 +    {
    2.27 +    }
    2.28 +    
    2.29 +template <typename T>
    2.30 +Queue<T>::~Queue( void ) {
    2.31 +    assert( N == 0 );  // Catch the potential memory leak.
    2.32 +    while ( first ) {
    2.33 +        Node *next = first->next;
    2.34 +        delete first;
    2.35 +        first = next;
    2.36 +        }
    2.37 +    }
    2.38 +
    2.39 +template <typename T>
    2.40 +void Queue<T>::enqueue( T &item ) {
    2.41 +    Node * node = new Node();
    2.42 +    node->item = item;
    2.43 +    node->next = nullptr;
    2.44 +
    2.45 +    if ( last ) {
    2.46 +        last->next = node;
    2.47 +        last = node;
    2.48 +        }
    2.49 +    else {
    2.50 +        last = first = node;
    2.51 +        }
    2.52 +
    2.53 +    N++;
    2.54 +    }
    2.55 +
    2.56 +template <typename T>
    2.57 +T Queue<T>::dequeue( void ) {
    2.58 +    assert( N > 0 );
    2.59 +
    2.60 +    T item = first->item;
    2.61 +
    2.62 +    Node *old = first;
    2.63 +    first = first->next;
    2.64 +    delete old;
    2.65 +    N--;
    2.66 +
    2.67 +    if ( ! first )
    2.68 +        last = nullptr;
    2.69 +
    2.70 +    return item;
    2.71 +    }
    2.72 +
    2.73 +template <typename T>
    2.74 +bool Queue<T>::is_empty( void ) {
    2.75 +    return N == 0;
    2.76 +    }
    2.77 +
    2.78 +template <typename T>
    2.79 +size_t Queue<T>::size( void ) {
    2.80 +    return N;
    2.81 +    }
    2.82 +
    2.83 +template <typename T>
    2.84 +typename Queue<T>::iterator Queue<T>::begin( void ) {
    2.85 +    return Queue<T>::iterator( first );
    2.86 +    }
    2.87 +
    2.88 +template <typename T>
    2.89 +typename Queue<T>::iterator Queue<T>::end( void ) {
    2.90 +    return Queue<T>::iterator( nullptr );
    2.91 +    }
    2.92 +
    2.93 +
    2.94 +////////////////////////////////////////////////////////////////////////////////
    2.95 +
    2.96 +template <typename T>
    2.97 +Queue<T>::iterator::iterator( Node *c ) :
    2.98 +    curr (c)
    2.99 +    {
   2.100 +    }
   2.101 +
   2.102 +template <typename T>
   2.103 +typename Queue<T>::iterator & Queue<T>::iterator::operator++() {
   2.104 +    if ( this->curr != nullptr ) {
   2.105 +        this->curr = this->curr->next;
   2.106 +        }
   2.107 +    return *this;
   2.108 +    }
   2.109 +
   2.110 +template <typename T>
   2.111 +typename Queue<T>::iterator Queue<T>::iterator::operator++( int ) {
   2.112 +    auto t = Queue<T>::iterator( *this );
   2.113 +
   2.114 +    if ( this->curr != nullptr ) {
   2.115 +        this->curr = this->curr->next;
   2.116 +        }
   2.117 +    return t;
   2.118 +    }
   2.119 +
   2.120 +template <typename T>
   2.121 +T Queue<T>::iterator::operator*() {
   2.122 +    return this->curr->item;
   2.123 +    }
   2.124 +
   2.125 +template <typename T>
   2.126 +bool Queue<T>::iterator::operator!=( typename Queue<T>::iterator other ) {
   2.127 +    return this->curr != other.curr;
   2.128 +    }
   2.129 +
   2.130  
   2.131  #endif
   2.132