Implement the stack, queue, and priority queue data structures with a linked list implementation to get the given test code in driver.cpp to work properly.

driver.cpp

stackLL.h

queueLL.h

priorityQueueLL.h

2. For each public method of each of the above classes, provide a big-Oh bound on the worst case run-time for that method in terms of the number of items n contained in the data structure at the time of the method call. Justify your bound in each case. You will not be graded on the efficiency of your implementations per say, but will lose points if your implementation is slower than a nave approach. Incorrect bounds will lose nearly all points for the entire assignment. Correct but obnoxiously loose bounds will lose a large number of points. If you are unsure about how to bound the worst case run time of a method, seek help from classmates or the professor. Note that the correct worst case bound depends on your own personal implementation. Thus, the correct answer may be different for each student.

driver.cpp-----------------

#include #include #include "stackLL.h" #include "queueLL.h" #include "priorityQueueLL.h" using namespace std;

int main() { /////////////Test code for stack /////////////// stackLL stk;

stk.push(5); stk.push(13); stk.push(7); stk.push(3); stk.push(2); stk.push(11);

cout << "Popping: " << stk.pop() << endl; cout << "Popping: " << stk.pop() << endl;

stk.push(17); stk.push(19); stk.push(23);

while( ! stk.empty() ) { cout << "Popping: " << stk.pop() << endl; }

// output order: 11,2,23,19,17,3,7,13,5

///////////////////////////////////////

//////////Test code for queue ///////////

queueLL Q;

Q.enqueue(1); Q.enqueue(2); Q.enqueue(3); cout << "Dequeuing: " << Q.dequeue() << endl; cout << "Dequeuing: " << Q.dequeue() << endl; Q.enqueue(4); Q.enqueue(5);

while( ! Q.empty() ) { cout << "Dequeuing: " << Q.dequeue() << endl; }

/////////////////////////////////////////

//////////Test code for priority queue/////

priorityQueueLL pQueue;

const int SIZE = 20;

//insert a bunch of random numbers for(int i=0; i { pQueue.insert( rand() ); }

//pull them back out.. while( ! pQueue.empty() ) { cout << pQueue.extractMin() << endl; }

priorityQueueLL pqs;

pqs.insert("whale"); pqs.insert("snake"); pqs.insert("buffalo"); pqs.insert("elmo"); pqs.insert("fire"); pqs.insert("waffle");

while( ! pqs.empty() ) { cout << pqs.extractMin() << endl; }

///////////////////////////////////////////

return 0; }

queueLL.H----------------

class queueLL { private: //put what you need here...

public: queueLL() {}

~queueLL() {}

//add item to back of queue enqueue(int x) {}

//remove and return first item from queue dequeue() {} }

priorityqueueLL.h------------------------------

template class priorityQueueLL { private: class node { public: //put what you need here.. }

//add what you wish here

public:

priorityQueue() {}

~priorityQueue() {}

//return true if empty, false if not bool empty() {}

//add item void insert(T x) {}

//remove and return smallest item T extractMin() {}

};

stackLL.h------------------------------------

class stackLL { private: class node { public: //put what you need in here };

node * top;

public:

stackLL() {}

//Take care of memory leaks... ~stackLL() {}

//return true if empty, false if not bool empty() {}

//add item to top of stack void push(int x) {}

//remove and return top item from stack int pop() {}

////////////////////////////// //additional "weird" methods: //////////////////////////////

//remove and return the kth item from the top of the stack. int popkth(int k) {}

//decimate: remove every 10th item from the stack void decimate() {}

//add item x to stack, but insert it //right after the current ith item from the top //(and before the i+1 item). void insertAt(int x, int i) {}

};