Data Structures -lab 10- Stacks and Queues Solved

lab 10: Stacks and Queues



Instructions: Implement a Stack and a Queue with whatever data structure you desire. Remember you may use code from a previous lab or STL vector/list (*hint* *hint*). In class we will implement a stack:

#ifndef STACK_H #define STACK_H

template<class T class Stack { private:

/* Class to implement.*/ public:

/* Empty constructor shall create an empty Stack! */ Stack();

/* Do a deep copy of stack into the this.

* Note: This one uses a reference to a Stack!

*/

Stack(const Stack<T &stack);

/* Deconstructor shall free up memory */

~Stack();

/* Return the current length (number of items) in the stack */ int getLength() const;

/* Returns true if the stack is empty. */ bool isEmpty() const; /* Print out the Stack */ void print() const;

/* Pushes the val to the top of the stack. */ bool push(const T &val);

/* Returns the top element from the stack. */ T& top();

/* Removes the top element from the stack. */ void pop();

/* Returns if the two stacks contain the same elements in the * same order.

*/ bool operator==(const Stack<T &stack) const;

};

#include "stack.cpp"

#endif
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

In your lab finish the implementation of a Queue:

#ifndef QUEUE_H #define QUEUE_H

template<class T class Queue { private:

/* Class to implement.*/ public:

/* Empty constructor shall create an empty Queue! */ Queue();

/* Do a deep copy of queue into the this.

* Note: This one uses a reference to a Queue!

*/

Queue(const Queue<T &queue);

/* Deconstructor shall free up memory */

~Queue();

/* Return the current length (number of items) in the queue */ int getLength() const;

/* Returns true if the queue is empty. */ bool isEmpty() const; /* Print out the Queue */ void print() const;

/* Pushes the val to the end of the queue. */ bool push(const T &val);

/* returns the first element from the queue. */ T& first();

/* Removes the first element from the queue. */ void pop();

/* Returns if the two queues contain the same elements in the * same order.

*/ bool operator==(const Queue<T &queue) const;

};

#include "queue.cpp"

#endif
39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

STL:

You may use vector, string, and list from the STL.

Write some test cases:

Create some test cases, using cxxtestgen, that you believe would cover all aspects of your code.

Memory Management:

Now that are using new, we must ensure that there is a corresponding delete to free the memory. Ensure there are no memory leaks in your code! Please run Valgrind on your tests to ensure no memory leaks!

How to turn in:

Turn in via GitHub. Ensure the file(s) are in your directory and then:

•    $ git add <files

•    $ git commit

•    $ git push