$30
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
