Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
Implementing Abstract Data Types with Linked Lists. Goals: -review abstract data types such as stacks, queues, -review programming with linked data structures -apply big-Oh analysis to your methods

Implementing Abstract Data Types with Linked Lists. Goals: -review abstract data types such as stacks, queues, -review programming with linked data structures -apply big-Oh analysis to your methods

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question

All files are included below, seperated by the dashes. "----"

//driver.cpp 


#include <iostream>
#include <string>
#include "stackLL.h"
#include "queueLL.h"
#include "priorityQueueLL.h"
using namespace std;

int main()
{
/////////////Test code for stack ///////////////
stackLLstk;

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


stackLLstkx;

stkx.push(5);
stkx.push(10);
stkx.push(15);
stkx.push(20);
stkx.push(25);
stkx.push(30);

stkx.insertAt(-100, 3);
stkx.insertAt(-200, 7);
stkx.insertAt(-300, 0);

//output order: -300,30,25,20,-100,15,10,5,-200
while( ! stkx.empty() )
cout<<"Popping: "<<stkx.pop() <<endl;


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

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

queueLLQ;

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

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

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



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

priorityQueueLL<int> pQueue;

constintSIZE = 20;

//insert a bunch of random numbers
for(inti=0; i<SIZE; i++)
{
pQueue.insert( rand() );
}

//pull them back out..
//They must come out in order from smallest to largest
while( ! pQueue.empty() )
{
cout << pQueue.extractMin() << endl;
}


priorityQueueLL<string> pqs;

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

//buffalo elmo fire snake waffle whale
while( ! pqs.empty() )
{
cout << pqs.extractMin() << endl;
}

///////////////////////////////////////////
//1) Template your queue class
//2) Add a decimate method to your queue class
queueLL<int> qx;

for(inti=1; i<=100; i++)
qx.enqueue( i );

//Eliminate every 10th item from list
//https://en.wikipedia.org/wiki/Decimation_(punishment)
qx.decimate();

//1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 21 22... 98 99
while( ! qx.empty() )
cout << qx.dequeue() << endl;


queueLL<string> qy;
qy.enqueue("sparticus");
qy.enqueue("maximus");
qy.enqueue("killicus");
qy.enqueue("awesomeicus");
qy.enqueue("gannicus");
qy.enqueue("varro");
qy.enqueue("oenomous");
qy.enqueue("slayicus");
qy.enqueue("bladeicus");
qy.enqueue("ted");
qy.enqueue("smashicus");
qy.enqueue("mallicus");
qy.enqueue("wussicus");
qy.enqueue("wimpicus");
qy.enqueue("crixus");

qy.decimate();

//Everyone but Ted.
while( ! qy.empty() )
cout << qy.dequeue() << endl;

return0;
}
--------------------------------------------------------------------------------------
//priorityQueueLL.h
 

template <class T>
class priorityQueueLL
{
private:
classnode
{
public:
//put what you need here..
}

//add what you wish here

public:

priorityQueueLL()
{}

~priorityQueueLL()
{}

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

//add item
voidinsert(Tx)
{}

//remove and return smallest item
TextractMin()
{}

};
------------------------------------------------------------------------------------
 
//queueLL.h
 
 

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

public:
queueLL()
{}

~queueLL()
{}

//add item to back of queue
voidenqueue(intx)
{}

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

//For the final part of the test program, template this class
//and add a decimate method.

};
 
---------------------------------------------------------------------------------------
 
//stackLL.h
 


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

node * top;

public:

stackLL()
{}

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

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

//add item to top of stack
voidpush(intx)
{}

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

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

};
--------------------------------------------------------------------
 
Implementing Abstract Data Types with Linked Lists. Goals: -review abstract data types such as stacks, queues, and priority queues. -review programming with linked data structures -apply big-Oh analysis to your methods -review c++ templated classes (the priorityQueueLL class must be a template) Turn-in: Submit your source code to blackboard, along with a document analyzing the big-oh run time for each of your methods. 1. 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 naïve 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.
Transcribed Image Text:Implementing Abstract Data Types with Linked Lists. Goals: -review abstract data types such as stacks, queues, and priority queues. -review programming with linked data structures -apply big-Oh analysis to your methods -review c++ templated classes (the priorityQueueLL class must be a template) Turn-in: Submit your source code to blackboard, along with a document analyzing the big-oh run time for each of your methods. 1. 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 naïve 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.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Randomized Select Algorithm
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS