Mercurial > Algorithms__Sedgewick
annotate algs4-c++/src/Queue.hpp @ 8:b02533162b6e
Linked list based Queue class.
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Fri, 29 May 2015 21:13:32 -0500 |
| parents | |
| children | 0f99a5ae6cd4 |
| rev | line source |
|---|---|
| discordia@8 | 1 #ifndef QUEUE_HPP |
| discordia@8 | 2 #define QUEUE_HPP |
| discordia@8 | 3 |
| discordia@8 | 4 #include <cstddef> |
| discordia@8 | 5 |
| discordia@8 | 6 // Linked list based queue after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3 |
| discordia@8 | 7 |
| discordia@8 | 8 template <typename T> |
| discordia@8 | 9 class Queue { |
| discordia@8 | 10 |
| discordia@8 | 11 public: |
| discordia@8 | 12 |
| discordia@8 | 13 //////////////////////////////////// |
| discordia@8 | 14 class Node { |
| discordia@8 | 15 public: |
| discordia@8 | 16 T item; |
| discordia@8 | 17 Node *next; |
| discordia@8 | 18 }; |
| discordia@8 | 19 |
| discordia@8 | 20 |
| discordia@8 | 21 //////////////////////////////////// |
| discordia@8 | 22 class iterator; |
| discordia@8 | 23 friend class iterator; |
| discordia@8 | 24 class iterator { |
| discordia@8 | 25 |
| discordia@8 | 26 public: |
| discordia@8 | 27 |
| discordia@8 | 28 iterator( Node *c ); |
| discordia@8 | 29 |
| discordia@8 | 30 iterator& operator++(); |
| discordia@8 | 31 iterator operator++(int); |
| discordia@8 | 32 |
| discordia@8 | 33 T operator*(); |
| discordia@8 | 34 bool operator!=( typename Queue<T>::iterator ); |
| discordia@8 | 35 |
| discordia@8 | 36 private: |
| discordia@8 | 37 |
| discordia@8 | 38 Node *curr; |
| discordia@8 | 39 }; |
| discordia@8 | 40 |
| discordia@8 | 41 //////////////////////////////////// |
| discordia@8 | 42 |
| discordia@8 | 43 Queue( void ); |
| discordia@8 | 44 ~Queue( void ); |
| discordia@8 | 45 |
| discordia@8 | 46 void enqueue( T &item ); |
| discordia@8 | 47 T dequeue( void ); |
| discordia@8 | 48 |
| discordia@8 | 49 bool is_empty( void ); |
| discordia@8 | 50 size_t size( void ); |
| discordia@8 | 51 |
| discordia@8 | 52 iterator begin( void ); |
| discordia@8 | 53 iterator end( void ); |
| discordia@8 | 54 |
| discordia@8 | 55 private: |
| discordia@8 | 56 |
| discordia@8 | 57 size_t N; |
| discordia@8 | 58 Node *first; |
| discordia@8 | 59 Node *last; |
| discordia@8 | 60 |
| discordia@8 | 61 }; |
| discordia@8 | 62 |
| discordia@8 | 63 |
| discordia@8 | 64 |
| discordia@8 | 65 #endif |
| discordia@8 | 66 |