For those of you going to to study Computer Science and are thinking about the d

Question

For those of you going to to study Computer Science and are thinking about the data structures class this project will give you an introduction. There are two important data structures that you will learn and use. The first is a stack, it is a LIFO (Last In First Out) structure. You can think of it like a a stack of plates in your cabinet. You pile plates on top of each other when you put them away and you take a plate from the top of the pile when you need to use one. This functionality is called push (add to the top of the stack) and pop ( remove from the top of stack). There is one last function that most stacks have. This function is called peek because it will allow you to see what is at the top of the stack without removing it.

The other popular data structure is called a queue. The queue is a FIFO (First In First Out) data structure and you can think of it like standing in line at Disneyland. If you are fortunate enough to be first in line then you are the first person to get on the ride. You will see the stack and the queue all over computers if you study operating systems. The stack is used to store and keep track of variables and the queue is used to store data that is waiting to be processed. This is just to name a couple. In the operating system tasks that are being scheduled to run are put into the queue. There is a slight difference in that many of these queues are called priority queues in that each taks added to the queue is assigned a priority. The higher the priority a task has, the closer it gets to the front of the queue.

Your task is to create a priority queue class calle priQueue that is derived from the vector class. Your class should be constructed as a template class so that the type of data the queue operates on can easily be changed:

priQueue iQueue; // holds ints

priQueue sQueue; // holds string.

Your priority queue should be sorted by priority based on a value from 1 to 10. If a number is assigned that is outside the range of 1 to 10 you should give the element a value of 5. What this means is that each time an element is added to the queue it should be put in order by priority. If multiple elements are given the same priority their position relative to each other is unimportant as long as they are prioritized relative to other elements in the queue.

Your priQueue should have the following functionallity:

Specifics

You should create a struct called qElem that will hold both the priority of the element and the data to be put in the queue. The struct should also be of template type so that the value it holds can be of any type. The priority variable type should be an int.

The priQueue class should be derived from vector and should also be a template class so that it can operate on any type. The enque function should be adding a qElem struct so that the data and the prority are coupled. This needs to be done so that the data and priority are related for sorting. Here is an example:

priQueue que;;

que.enqueue("Hello", 3);
que.enqueue("Goodbye", 9); // You are passing a string an an int but you should store a qElem struct.

string s = que.dequeue();

The string s at this point should hold "Goodbye" even though it was put in last because it has a higher priority.

Sorting your queue. You are to create your own sort functionality. Pick any sort that you would like but the bubble sort might be the easiest to implement.

NOTE:

Your priQueue class should be derived from the vector class that is part of the std namespace.

Explanation / Answer

/*A simple priority Queue class. Using a vector to store keys ensures that data structure can grow dynamically. Also see we have vector of int. In a real world example we will have vector of some real items like process information for doing scheduling based on priority.*/ class PriorityQueue { vector pq_keys; void shiftRight(int low, int high); void shiftLeft(int low, int high); void buildHeap(); public: PriorityQueue(){} PriorityQueue(vector& items) { pq_keys = items; buildHeap(); } /*Insert a new item into the priority queue*/ void enqueue(int item); /*Get the maximum element from the priority queue*/ int dequeue(); /*Just for testing*/ void print(); }; void PriorityQueue::enqueue(int item) { pq_keys.push_back(item); shiftLeft(0, pq_keys.size() - 1); return; } int PriorityQueue::dequeue() { assert(pq_keys.size() != 0); int last = pq_keys.size() - 1; int tmp = pq_keys[0]; pq_keys[0] = pq_keys[last]; pq_keys[last] = tmp; pq_keys.pop_back(); shiftRight(0, last-1); return tmp; } void PriorityQueue::print() { int size = pq_keys.size(); for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.