1 #ifndef STACK_HPP

2 #define STACK_HPP

3

4 #include <cstddef>

5

6 // Linked list based stack after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2

7

8 template <typename T>

9 class Stack {

10

11 private:

12

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

14 class Node {

15 public:

16 T item;

17 Node *next;

18 };

19

20

21 public:

22

23 ////////////////////////////////////

24 class iterator;

25 friend class iterator;

26 class iterator {

27

28 public:

29

30 iterator( Node *c );

31

32 iterator& operator++();

33 iterator operator++(int);

34

35 T operator*();

36 bool operator!=( typename Stack<T>::iterator );

37

38 private:

39

40 Node *curr;

41 };

42

43 ////////////////////////////////////

44

45 Stack( void );

46 ~Stack( void );

47

48 void push( T &item );

49 T pop( void );

50

51 bool is_empty( void );

52 size_t size( void );

53

54 iterator begin( void );

55 iterator end( void );

56

57 #ifdef EXERCISES

58

59 T delete_bottom( void ); // 1.3.19

60 T remove( size_t k ); // 1.3.20

61 bool find( T key ); // 1.3.21

62

63 #endif

64

65 private:

66

67 size_t N;

68 Node *list;

69

70 };

71

72

73

74 #endif

75