lab 11: Queues
Instructions: Implement a Queue with whatever data structure you desire. Remember you may use code from a previous lab (*hint* *hint*).
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; /* Add a value to the queue with respect to priority.
* For this function a lower number is a higher priority.
* EX: If the Queue is of integers and is { 5, 10, 15} and I add 7, * the new queue is { 5, 7, 10, 15}.
*/ void addWithPriority(const T& val);
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
39
/* Return the length of the shortest path, but with warps. The map is
* a 2D array with each cell having the following property
* 0: Cell is open (passable) * -1: Cell is a wall (impassable) * 0: Cell is a warp.
* A warp is a value 999 and warps to the position * (<first three digits, second three digits).
* Hence 1000 warps to (1, 0), and 203109 warps to (203, 109)
* To get the x value: <cell/1000
* To get the y value: <cell%1000 * Note: Taking a warp costs 1.
*/ int getShortestPathWithWarps(int **map, int width, int length, int sx, int sy, int ex, int ey);
};
#include "queue.cpp"
#endif
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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
