Data Strucrues-lab 11 - Queues Solved

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