Mercurial > Algorithms__Sedgewick
annotate 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 |
rev | line source |
---|---|
discordia@12 | 1 #ifndef DEQUE_HPP |
discordia@12 | 2 #define DEQUE_HPP |
discordia@12 | 3 |
discordia@12 | 4 #include <cstddef> |
discordia@12 | 5 |
discordia@12 | 6 // Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3 |
discordia@12 | 7 |
discordia@12 | 8 template <typename T> |
discordia@12 | 9 class Deque { |
discordia@12 | 10 |
discordia@12 | 11 private: |
discordia@12 | 12 |
discordia@12 | 13 //////////////////////////////////// |
discordia@12 | 14 class Node { |
discordia@12 | 15 public: |
discordia@12 | 16 T item; |
discordia@12 | 17 Node *next; |
discordia@12 | 18 Node *prev; |
discordia@12 | 19 }; |
discordia@12 | 20 |
discordia@12 | 21 public: |
discordia@12 | 22 |
discordia@12 | 23 //////////////////////////////////// |
discordia@12 | 24 class iterator; |
discordia@12 | 25 friend class iterator; |
discordia@12 | 26 class iterator { |
discordia@12 | 27 |
discordia@12 | 28 public: |
discordia@12 | 29 |
discordia@12 | 30 iterator( Node *c ); |
discordia@12 | 31 |
discordia@12 | 32 iterator& operator++(); |
discordia@12 | 33 iterator operator++(int); |
discordia@12 | 34 |
discordia@12 | 35 T operator*(); |
discordia@12 | 36 bool operator!=( typename Deque<T>::iterator ); |
discordia@12 | 37 |
discordia@12 | 38 private: |
discordia@12 | 39 |
discordia@12 | 40 Node *curr; |
discordia@12 | 41 }; |
discordia@12 | 42 |
discordia@12 | 43 //////////////////////////////////// |
discordia@12 | 44 |
discordia@12 | 45 Deque( void ); |
discordia@12 | 46 ~Deque( void ); |
discordia@12 | 47 |
discordia@12 | 48 void push_left( T &item ); |
discordia@12 | 49 void push_right( T &item ); |
discordia@12 | 50 T pop_left( void ); |
discordia@12 | 51 T pop_right( void ); |
discordia@12 | 52 |
discordia@12 | 53 bool is_empty( void ); |
discordia@12 | 54 size_t size( void ); |
discordia@12 | 55 |
discordia@12 | 56 iterator begin( void ); |
discordia@12 | 57 iterator end( void ); |
discordia@12 | 58 |
discordia@12 | 59 |
discordia@12 | 60 private: |
discordia@12 | 61 |
discordia@12 | 62 size_t N; |
discordia@12 | 63 Node *first; |
discordia@12 | 64 Node *last; |
discordia@12 | 65 |
discordia@12 | 66 }; |
discordia@12 | 67 |
discordia@12 | 68 |
discordia@12 | 69 |
discordia@12 | 70 #endif |
discordia@12 | 71 |