Mercurial > Algorithms__Sedgewick

annotate algs4-c++/src/Deque.hpp @ 12:1e3c509b6ac4

find changesets by author, revision, files, or words in the commit message
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