Mercurial > Algorithms__Sedgewick
diff algs4-c++/src/Deque.hpp @ 12:1e3c509b6ac4
Added Deque (exercise 1.3.33)
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Wed, 10 Jun 2015 15:44:42 -0500 |
parents | |
children | a149b424b4e2 |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/algs4-c++/src/Deque.hpp Wed Jun 10 15:44:42 2015 -0500 1.3 @@ -0,0 +1,71 @@ 1.4 +#ifndef DEQUE_HPP 1.5 +#define DEQUE_HPP 1.6 + 1.7 +#include <cstddef> 1.8 + 1.9 +// Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3 1.10 + 1.11 +template <typename T> 1.12 +class Deque { 1.13 + 1.14 +private: 1.15 + 1.16 + //////////////////////////////////// 1.17 + class Node { 1.18 + public: 1.19 + T item; 1.20 + Node *next; 1.21 + Node *prev; 1.22 + }; 1.23 + 1.24 +public: 1.25 + 1.26 + //////////////////////////////////// 1.27 + class iterator; 1.28 + friend class iterator; 1.29 + class iterator { 1.30 + 1.31 + public: 1.32 + 1.33 + iterator( Node *c ); 1.34 + 1.35 + iterator& operator++(); 1.36 + iterator operator++(int); 1.37 + 1.38 + T operator*(); 1.39 + bool operator!=( typename Deque<T>::iterator ); 1.40 + 1.41 + private: 1.42 + 1.43 + Node *curr; 1.44 + }; 1.45 + 1.46 + //////////////////////////////////// 1.47 + 1.48 + Deque( void ); 1.49 + ~Deque( void ); 1.50 + 1.51 + void push_left( T &item ); 1.52 + void push_right( T &item ); 1.53 + T pop_left( void ); 1.54 + T pop_right( void ); 1.55 + 1.56 + bool is_empty( void ); 1.57 + size_t size( void ); 1.58 + 1.59 + iterator begin( void ); 1.60 + iterator end( void ); 1.61 + 1.62 + 1.63 +private: 1.64 + 1.65 + size_t N; 1.66 + Node *first; 1.67 + Node *last; 1.68 + 1.69 + }; 1.70 + 1.71 + 1.72 + 1.73 +#endif 1.74 +