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 public:

12

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

14 class Node {

15 public:

16 T item;

17 Node *next;

18 };

19

20

21 ////////////////////////////////////

22 class iterator;

23 friend class iterator;

24 class iterator {

25

26 public:

27

28 iterator( Node *c );

29

30 iterator& operator++();

31 iterator operator++(int);

32

33 T operator*();

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

35

36 private:

37

38 Node *curr;

39 };

40

41 ////////////////////////////////////

42

43 Queue( void );

44 ~Queue( void );

45

46 void enqueue( T &item );

47 T dequeue( void );

48

49 bool is_empty( void );

50 size_t size( void );

51

52 iterator begin( void );

53 iterator end( void );

54

55 private:

56

57 size_t N;

58 Node *first;

59 Node *last;

60

61 };

62

63

64

65 #endif

66