1 #ifndef QUEUE_HPP

2 #define QUEUE_HPP

3

4 #include <cstddef>

5

6 // Linked list based queue after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3

7

8 template <typename T>

9 class Queue {

10

11 private:

12

13 ////////////////////////////////////

14 class Node {

15 public:

16 T item;

17 Node *next;

18 };

19

20 public:

21

22 ////////////////////////////////////

23 class iterator;

24 friend class iterator;

25 class iterator {

26

27 public:

28

29 iterator( Node *c );

30

31 iterator& operator++();

32 iterator operator++(int);

33

34 T operator*();

35 bool operator!=( typename Queue<T>::iterator );

36

37 private:

38

39 Node *curr;

40 };

41

42 ////////////////////////////////////

43

44 Queue( void );

45 ~Queue( void );

46

47 void enqueue( T &item );

48 T dequeue( void );

49

50 bool is_empty( void );

51 size_t size( void );

52

53 iterator begin( void );

54 iterator end( void );

55

56

57 private:

58

59 size_t N;

60 Node *first;

61 Node *last;

62

63 };

64

65

66

67 #endif

68