I need help with the following:

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..

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) {}

};