1.1 --- a/algs4-c++/src/Queue.hpp	Tue Jun 23 12:28:03 2015 -0500
     1.2 +++ b/algs4-c++/src/Queue.hpp	Tue Jun 23 14:52:17 2015 -0500
     1.3 @@ -5,6 +5,7 @@
     1.4  
     1.5  #include <cstddef>
     1.6  #include <cassert>
     1.7 +#include <iterator>
     1.8  
     1.9  template <typename T>
    1.10  class Queue {
    1.11 @@ -21,9 +22,7 @@
    1.12  public:
    1.13  
    1.14      ////////////////////////////////////
    1.15 -    class iterator;
    1.16 -    friend class iterator;
    1.17 -    class iterator {
    1.18 +    class iterator : public std::iterator<std::forward_iterator_tag, T> {
    1.19  
    1.20      public:
    1.21  
    1.22 @@ -42,9 +41,31 @@
    1.23  
    1.24      ////////////////////////////////////
    1.25  
    1.26 +    class const_iterator : public std::iterator<std::forward_iterator_tag, T> {
    1.27 +
    1.28 +    public:
    1.29 +
    1.30 +        const_iterator( const Node *c );
    1.31 +
    1.32 +        const_iterator& operator++();
    1.33 +        const_iterator operator++(int);
    1.34 +
    1.35 +        const T operator*();
    1.36 +        bool operator!=( typename Queue<T>::const_iterator );
    1.37 +
    1.38 +    private:
    1.39 +
    1.40 +        const Node *curr;
    1.41 +        };
    1.42 +
    1.43 +    ////////////////////////////////////
    1.44 +
    1.45      Queue( void );
    1.46      ~Queue( void );
    1.47  
    1.48 +    // 1.3.41 Copy constructor.
    1.49 +    Queue( const Queue<T> &q );
    1.50 +
    1.51      void enqueue( T &item );
    1.52      T dequeue( void );
    1.53  
    1.54 @@ -53,6 +74,8 @@
    1.55  
    1.56      iterator begin( void );
    1.57      iterator end( void );
    1.58 +    const_iterator begin( void ) const;
    1.59 +    const_iterator end( void ) const;
    1.60  
    1.61  
    1.62  private:
    1.63 @@ -71,6 +94,19 @@
    1.64      last (nullptr)
    1.65      {
    1.66      }
    1.67 +
    1.68 +// 1.3.41
    1.69 +template <typename T>
    1.70 +Queue<T>::Queue( const Queue<T> &q ) :
    1.71 +    N (0),
    1.72 +    first (nullptr),
    1.73 +    last (nullptr)
    1.74 +    {
    1.75 +    for ( auto it = q.begin(); it != q.end(); ++it ) {
    1.76 +        T item = *it;    
    1.77 +        this->enqueue( item );
    1.78 +        }
    1.79 +    }
    1.80      
    1.81  template <typename T>
    1.82  Queue<T>::~Queue( void ) {
    1.83 @@ -136,6 +172,16 @@
    1.84      return Queue<T>::iterator( nullptr );
    1.85      }
    1.86  
    1.87 +template <typename T>
    1.88 +typename Queue<T>::const_iterator Queue<T>::begin( void ) const {
    1.89 +    return Queue<T>::const_iterator( first );
    1.90 +    }
    1.91 +
    1.92 +template <typename T>
    1.93 +typename Queue<T>::const_iterator Queue<T>::end( void ) const {
    1.94 +    return Queue<T>::const_iterator( nullptr );
    1.95 +    }
    1.96 +
    1.97  
    1.98  ////////////////////////////////////////////////////////////////////////////////
    1.99  
   1.100 @@ -173,6 +219,42 @@
   1.101      return this->curr != other.curr;
   1.102      }
   1.103  
   1.104 +////////////////////////////////////////////////////////////////////////////////
   1.105 +
   1.106 +template <typename T>
   1.107 +Queue<T>::const_iterator::const_iterator( const Node *c ) :
   1.108 +    curr (c)
   1.109 +    {
   1.110 +    }
   1.111 +
   1.112 +template <typename T>
   1.113 +typename Queue<T>::const_iterator & Queue<T>::const_iterator::operator++() {
   1.114 +    if ( this->curr != nullptr ) {
   1.115 +        this->curr = this->curr->next;
   1.116 +        }
   1.117 +    return *this;
   1.118 +    }
   1.119 +
   1.120 +template <typename T>
   1.121 +typename Queue<T>::const_iterator Queue<T>::const_iterator::operator++( int ) {
   1.122 +    auto t = Queue<T>::const_iterator( *this );
   1.123 +
   1.124 +    if ( this->curr != nullptr ) {
   1.125 +        this->curr = this->curr->next;
   1.126 +        }
   1.127 +    return t;
   1.128 +    }
   1.129 +
   1.130 +template <typename T>
   1.131 +const T Queue<T>::const_iterator::operator*() {
   1.132 +    return this->curr->item;
   1.133 +    }
   1.134 +
   1.135 +template <typename T>
   1.136 +bool Queue<T>::const_iterator::operator!=( typename Queue<T>::const_iterator other ) {
   1.137 +    return this->curr != other.curr;
   1.138 +    }
   1.139 +
   1.140  
   1.141  #endif
   1.142