Template Dequeue Class (C++ )
In this assignment, we will use a given test menu for the template Deque Class (a Linked List based Double Ended Queue, Deque) that you have put together.
Starter
testDeque.cpp which contains:
- Timer class holder (you need to go through the LearnCpp Ch15 and import it in)
- Node class
- Deque class specification (you need to fill out the definition)
here is the testDeque.cpp code:
| // C++ implementation of doubly linked list Deque doubly linked list | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| class Timer { | |
| // To replace with the full timer class definition | |
| // inside this folder: LearnCpp9_18_timeSortArray.cpp | |
| }; | |
| // Node of a doubly linked list | |
| template<class T> | |
| class Node { | |
| public: | |
| T data; | |
| Node<T> *prev, *next; | |
| static Node<T>* getnode(int data) { | |
| Node<T>* n = new Node<T>; | |
| n->data = data; | |
| n->prev = n->next = nullptr; | |
| return n; | |
| } | |
| }; | |
| // A doubly linked list deque | |
| template<class T> | |
| class Deque { | |
| Node<T> *head, *tail, *copy; | |
| int size; | |
| // deep copy helper | |
| void deepCopy( const Deque<T> & rhs ); | |
| public: | |
| Deque():head(nullptr), tail(nullptr), size(0) { } | |
| Deque( const Deque<T> & rhs ); // copy constructor | |
| Deque( Deque<T> && rhs ); // move constructor | |
| Deque<T> & operator= ( Deque<T> & rhs ); // copy operator= | |
| Deque<T> & operator= ( Deque<T> && rhs ); // move operator= | |
| // Operations on Deque | |
| void pushHead(T data); | |
| void pushTail(T data); | |
| void popHead(); | |
| void popTail(); | |
| void erase(); | |
| T getFront(); | |
| T getRear(); | |
| int _size() { return size; } | |
| bool isEmpty() { return !head; } | |
| T operator[] (const int &sub); | |
| }; | |
| template<class T> | |
| void Deque<T>::deepCopy( const Deque<T> & rhs ) { | |
| Node<T> *newNode = new Node<T>; | |
| Node<T> *current = rhs.head; //current points to the list to be copied | |
| size = rhs.size;//copy the head node | |
| copy = newNode; //create the node | |
| copy->data = current->data; //copy the info | |
| copy->next = current->next; //set the link field of the node to nullptr | |
| copy->prev = current->prev; | |
| tail = head; //make tail point to the head node | |
| current = current->next; //make current point to the next node | |
| //copy the remaining list | |
| while (current != nullptr) { | |
| newNode = new Node<T>; //create a node | |
| newNode->data = current->data; //copy the info | |
| newNode->next = current->next; | |
| newNode->prev = current->prev; | |
| tail->next = newNode; | |
| tail = newNode; | |
| current = current->next; | |
| } | |
| } | |
| // complete the rest of definitions below | |
| // Driver program to test the Link List Deque class | |
| int main() { | |
| Deque<int> dq; | |
| cout << "\nInsert item '5' at tail"; | |
| dq.pushTail(5); | |
| cout << "\nInsert item '10' at tail"; | |
| dq.pushTail(10); | |
| cout << "\nRear item: " << dq.getRear(); | |
| dq.popTail(); | |
| cout << "\nAfter deleting tail item, new tail is " | |
| << dq.getRear(); | |
| cout << "\nInserting item '15' in head"; | |
| dq.pushHead(15); | |
| cout << "\nFront item: " << dq.getFront() | |
| << "\nNumber of items in Deque: " << dq._size(); | |
| dq.popHead(); | |
| cout << "\nAfter deleting head item new head is " | |
| << dq.getFront(); | |
| dq.popHead(); | |
| cout << "\nAfter deleting head item new head is " | |
| << dq.getFront(); | |
| cout << "\nInitializing a 10000 item Deque."; | |
| Timer t1; | |
| for(int i=1; i<=10000; i++) dq.pushTail(i); | |
| cout << "\nAdd 1~10000, dq now has " | |
| << dq._size() << " items."; | |
| double run1 = t1.elapsed(); | |
| cout << "\nTime elipsed: " << run1 << " seconds"; | |
| Timer t2; | |
| cout << "\nDeep Copy construct dq2"; | |
| Deque<int> dq2( dq ); | |
| double run2 = t2.elapsed(); | |
| cout << "\nTime elipsed: " << run2 << " seconds" | |
| << "\ndq2 front to rear: " << dq2.getFront() | |
| << " to " << dq2.getRear(); | |
| cout << "\nMove construct dq3"; | |
| Timer t3; | |
| Deque<int> dq3(std::move(dq)); | |
| double run3 = t3.elapsed(); | |
| cout << "\nTime elipsed: " << run3 << " seconds" | |
| << "\ndq3 front to rear: " << dq3.getFront() | |
| << " to " << dq3.getRear(); | |
| cout << "\ndq2[0] is " << dq2[0] | |
| << ", dq2[999] is " << dq2[999]; | |
| } |
Make sure you have implemented and validated the Stack/Queue member functions especially the following additional methods for AS 9:
- subscription operator [ ] read and write (included instarter)
- subscription over the range exception (included in starter)
Example Test Driver
// Driver program to test the Link List Deque class
int main() {
Deque dq;
cout << "\nInsert item '5' at tail";
dq.pushTail(5);
cout << "\nInsert item '10' at tail";
dq.pushTail(10);
cout << "\nRear item: " << dq.getRear();
dq.popTail();
cout << "\nAfter deleting tail item, new tail is "
<< dq.getRear();
cout << "\nInserting item '15' in head";
dq.pushHead(15);
cout << "\nFront item: " << dq.getFront()
<< "\nNumber of items in Deque: " << dq._size();
dq.popHead();
cout << "\nAfter deleting head item new head is "
<< dq.getFront();
dq.popHead();
cout << "\nAfter deleting head item new head is "
<< dq.getFront();
cout << "\nInitializing a 10000 item Deque.";
Timer t1;
for(int i=1; i<=10000; i++) dq.pushTail(i);
cout << "\nAdd 1~10000, dq now has "
<< dq._size() << " items.";
double run1 = t1.elapsed();
cout << "\nTime elipsed: " << run1 << " seconds";
Timer t2;
cout << "\nDeep Copy construct dq2";
Deque dq2( dq );
double run2 = t2.elapsed();
cout << "\nTime elipsed: " << run2 << " seconds"
<< "\ndq2 front to rear: " << dq2.getFront()
<< " to " << dq2.getRear();
cout << "\nMove construct dq3";
Timer t3;
Deque dq3(std::move(dq));
double run3 = t3.elapsed();
cout << "\noisy()Time elipsed: " << run3 << " seconds"
<< "\ndq3 front to rear: " << dq3.getFront()
<< " to " << dq3.getRear();
cout << "\ndq2[0] is " << dq2[0]
<< ", dq2[999] is " << dq2[999];
}
Sample Test Run
Submit
- AS10_testDeque.cpp
- Deque.h and Timer.h
- test run validation
Homework Answers
// Deque.h
#include <bits/stdc++.h>
using namespace std;
class Timer {
// Add the code for Timer
// To replace with the full timer class definition
// inside this folder: LearnCpp9_18_timeSortArray.cpp
};
// Node of a doubly linked list
template<class T>
class Node {
public:
T data;
Node<T> *prev, *next;
static Node<T>* getnode(int data) {
Node<T>* n = new Node<T>;
n->data = data;
n->prev = n->next = nullptr;
return n;
}
};
// A doubly linked list deque
template<class T>
class Deque {
Node<T> *head, *tail, *copy;
int size;
// deep copy helper
void deepCopy( const Deque<T> & rhs );
public:
Deque():head(nullptr), tail(nullptr), size(0) { }
Deque( const Deque<T> & rhs ); // copy constructor
Deque( Deque<T> && rhs ); // move constructor
Deque<T> & operator= ( Deque<T> & rhs ); // copy operator=
Deque<T> & operator= ( Deque<T> && rhs ); // move operator=
// Operations on Deque
void pushHead(T data);
void pushTail(T data);
void popHead();
void popTail();
void erase();
T getFront();
T getRear();
int _size() { return size; }
bool isEmpty() { return !head; }
T operator[] (const int &sub);
//~Deque(){erase();}
};
template<class T>
void Deque<T>::deepCopy( const Deque<T> & rhs ) {
Node<T> *newNode = new Node<T>;
Node<T> *current = rhs.head; //current points to the list to be copied
size = rhs.size;//copy the head node
copy = newNode; //create the node
copy->data = current->data; //copy the info
copy->next = current->next; //set the link field of the node to nullptr
copy->prev = current->prev;
head = copy;
tail = head; //make tail point to the head node
current = current->next; //make current point to the next node
//copy the remaining list
while (current != nullptr) {
newNode = new Node<T>; //create a node
newNode->data = current->data; //copy the info
newNode->next = current->next;
newNode->prev = current->prev;
tail->next = newNode;
tail = newNode;
current = current->next;
}
}
template <class T>
Deque<T>:: Deque( const Deque<T> & rhs )
{
head = nullptr;
tail = nullptr;
size = 0;
deepCopy(rhs);
}
template <class T>
Deque<T>::Deque( Deque<T> && rhs ) : head(nullptr),tail(nullptr), size(0)
{
head = rhs.head;
size = rhs.size;
tail = rhs.tail;
copy = rhs.copy;
rhs.head = nullptr;
rhs.size = 0;
rhs.tail = nullptr;
rhs.copy = nullptr;
}
template <class T>
Deque<T>& Deque<T>:: operator= ( Deque<T> & rhs )
{
if(this != &rhs)
{
erase();
head = nullptr;
tail = nullptr;
size = 0;
copy = nullptr;
deepCopy(rhs);
}
return *this;
}
template <class T>
Deque<T>& Deque<T>:: operator= ( Deque<T> && rhs )
{
if(this != &rhs)
{
erase();
head = nullptr;
tail = nullptr;
copy = nullptr;
head = rhs.head;
tail = rhs.tail;
copy = rhs.copy;
size = rhs.size;
rhs.head = nullptr;
rhs.tail = nullptr;
rhs.copy = nullptr;
rhs.size = 0;
}
return *this;
}
// Operations on Deque
template <class T>
void Deque<T>::pushHead(T data)
{
Node<T> *newNode = new Node<T>;
newNode->data = data;
newNode->next = head;
newNode->prev = nullptr;
if(head == nullptr)
{
head = newNode;
tail = head;
}else
{
head->prev = newNode;
head = newNode;
}
size++;
}
template <class T>
void Deque<T>::pushTail(T data)
{
Node<T> *newNode = new Node<T>;
newNode->data = data;
newNode->next = nullptr;
newNode->prev = tail;
if(head == nullptr)
{
head = newNode;
tail = newNode;
}else
{
tail->next = newNode;
tail = newNode;
}
size++;
}
template <class T>
void Deque<T>::popHead()
{
if(head != nullptr)
{
Node<T> *temp = head;
head = head->next;
delete(temp);
if(head != nullptr)
head->prev= nullptr;
else
tail = nullptr;
size--;
}
}
template <class T>
void Deque<T>::popTail()
{
if(head != nullptr)
{
Node<T> *temp = tail;
tail = tail->prev;
delete(temp);
if(tail != nullptr)
tail->next = nullptr;
else
head = nullptr;
size--;
}
}
template <class T>
void Deque<T>::erase()
{
while(head != nullptr)
{
Node<T> *temp = head;
head = head->next;
delete(temp);
}
tail = nullptr;
copy = nullptr;
size = 0;
}
template <class T>
T Deque<T>::getFront()
{
if(head != nullptr)
{
return head->data;
}
return T(NULL);
}
template <class T>
T Deque<T>::getRear()
{
if(tail != nullptr)
{
return tail->data;
}
return T(NULL);
}
template <class T>
T Deque<T>::operator[] (const int &sub)
{
if(sub >=0 && sub <size)
{
Node<T> *current = head;
int pos = 0;
while(pos < sub)
{
current = current->next;
pos++;
}
return current->data;
}
return T(NULL);
}
//end of Deque.h
Add Answer to:
Template Dequeue Class (C++ ) In this assignment, we will use a given test menu for the template ...
Template Deque Class (C++) In this assignment, we will use a given test menu for the template Deq...
Template Deque Class (C++)
In this assignment, we will use a given test menu for the
template Deque Class (a Linked List based Double Ended Queue,
Deque) that you have put together.
Recommended Steps
testDeque.cpp :
// C++ implementation of doubly linked list Deque doubly linked
list
#include <bits/stdc++.h>
using namespace std;
class Timer {
// To replace with the full timer class definition
// inside this folder: LearnCpp9_18_timeSortArray.cpp
};
// Node of a doubly linked list
template<class T>
class...
Simple test in text: int main() { Deque dq1; cout << dq1.empty() << " - 1"...
Simple test in text:
int main()
{
Deque dq1;
cout << dq1.empty() << " - 1" << endl;
dq1.insertFront(42);
dq1.insertBack(216);
cout << dq1.peekFront() << " - 42" << endl;
cout << dq1.peekBack() << " - 216" << endl;
cout << dq1.size() << " - 2" << endl;
Deque dq2(dq1);
Deque dq3;
dq3 = dq1;
cout << dq1.removeFront() << " - 42" << endl;
cout << dq1.removeBack() << " - 216" << endl;
cout << dq2.peekFront() << " - 42" <<...
In C++, for the provided template linked list class create a derived class of it which...
In C++, for the provided template linked list class create a derived class of it which adds the functionality to it to find the high and low value of any given data stored in the list. The derived class must be a template. LinkedList.h #pragma once #include <iostream> using namespace std; template <class T> class ListNode { public: T data; ListNode<T>* next; ListNode(T data) { this->data = data;...
What is the specific answer for 1. and 2. Thanks! Add a new method, find, to...
What is the specific answer for 1. and 2. Thanks! Add a new method, find, to class SinglyLinkedList (defined here) that takes as input a “data” value and returns a pointer to a node. If the input data is present in the linked list, the returned pointer should point to that node; if not, the returned pointer is nullptr. Write the (single line) method declaration/specification. Write the method definition/implementation. Test by running the main() function below and capture the console...
Design and implement your own linked list class to hold a sorted list of integers in ascending order. The class should h...
Design and implement your own linked list class to hold a sorted list of integers in ascending order. The class should have member function for inserting an item in the list, deleting an item from the list, and searching the list for an item. Note: the search function should return the position of the item in the list (first item at position 0) and -1 if not found. In addition, it should member functions to display the list, check if...
In this assignment, you will implement a sort method on singly-linked and doubly-linked lists. Implement the...
In this assignment, you will implement a sort method on
singly-linked and doubly-linked lists.
Implement the following sort member function on a singly-linked
list:
void
sort(bool(*comp)(const
T &, const
T &) = defaultCompare);
Implement the following sort member function on a doubly-linked
list:
void
sort(bool(*comp)(const
T &, const
T &) = defaultCompare);
The sort(…) methods take as a parameter a comparator function,
having a default assignment of defaultCompare, a
static function defined as follows:
template <typename T>
static bool defaultCompare(const...
I have the following c++ data structures assignment: Copy Constructors, Destructors, and Assignment Operators An understanding...
I have the following c++ data structures assignment: Copy Constructors, Destructors, and Assignment Operators An understanding of how to implement copy constructors, destructors, and assignment operators is essential when working with data structures using dynamic memory allocation. Failure to implement these methods correctly can and probably will result in memory leaks. In this project, you are provided with a working implementation of a doubly-linked list in which the copy constructor, destructor, and assignment operator methods are not complete. To complete...
C++ program: Convert the classes to template classes #include <iostream> #include <string> using namespace std; class Node { private: int data; Node* next; public: Node(int...
C++ program: Convert the classes to template classes #include <iostream> #include <string> using namespace std; class Node { private: int data; Node* next; public: Node(int data) { this->data=data; this->next = 0; } int getData(){return data;} Node* getNext(){return next;} void setNext(Node* next){this->next=next;} }; class LinkedList { private: Node* head = 0; public: int isEmpty() {return head == 0;} void print() { Node* currNode = head; while(currNode!=0) { cout << currNode->getData() << endl; currNode = currNode->getNext(); } } void append(int data) {...
For the LinkedList class, create a getter and setter for the private member 'name', constructing your...
For the LinkedList class, create a getter and setter for the private member 'name', constructing your definitions based upon the following declarations respectively: std::string get_name() const; and void set_name(std::string); In the Main.cpp file, let's test your getter and setter for the LinkedLIst private member 'name'. In the main function, add the following lines of code: cout << ll.get_name() << endl; ll.make_test_list(); ll.set_name("My List"); cout << ll.get_name() << endl; Output should be: Test List My List Compile and run your code;...
in c++ please include all of the following " template class, template function, singly linked list,...
in c++ please include all of the following " template class, template function, singly linked list, the ADT stack, copy constructor, operator overloading, "try catch"and pointers Modify the code named "Stack using a Singly Linked List" to make the ADT Stack that is a template class has the code of the destructor in which each node is directly deleted without using any member function. As each node is deleted, the destructor displays the address of the node that is being...
Template Deque Class (C++)
In this assignment, we will use a given test menu for the
template Deque Class (a Linked List based Double Ended Queue,
Deque) that you have put together.
Recommended Steps
testDeque.cpp :
// C++ implementation of doubly linked list Deque doubly linked
list
#include <bits/stdc++.h>
using namespace std;
class Timer {
// To replace with the full timer class definition
// inside this folder: LearnCpp9_18_timeSortArray.cpp
};
// Node of a doubly linked list
template<class T>
class...
Simple test in text:
int main()
{
Deque dq1;
cout << dq1.empty() << " - 1" << endl;
dq1.insertFront(42);
dq1.insertBack(216);
cout << dq1.peekFront() << " - 42" << endl;
cout << dq1.peekBack() << " - 216" << endl;
cout << dq1.size() << " - 2" << endl;
Deque dq2(dq1);
Deque dq3;
dq3 = dq1;
cout << dq1.removeFront() << " - 42" << endl;
cout << dq1.removeBack() << " - 216" << endl;
cout << dq2.peekFront() << " - 42" <<...
In this assignment, you will implement a sort method on
singly-linked and doubly-linked lists.
Implement the following sort member function on a singly-linked
list:
void
sort(bool(*comp)(const
T &, const
T &) = defaultCompare);
Implement the following sort member function on a doubly-linked
list:
void
sort(bool(*comp)(const
T &, const
T &) = defaultCompare);
The sort(…) methods take as a parameter a comparator function,
having a default assignment of defaultCompare, a
static function defined as follows:
template <typename T>
static bool defaultCompare(const...
Most questions answered within 3 hours.
-
what would be the best entry mode in shipping from the U.S to Spain
by boat...
asked 1 minute ago -
Under certain conditions, the substance ammonium
nitrate can be broken down to form dinitrogen
monoxide and...
asked 2 minutes ago -
1. A boy stands on one end of a boat, and then walks to the
other...
asked 12 minutes ago -
Casey is on trial under criminal allegations that she engaged in
fraudulent behavior at the company...
asked 17 minutes ago -
Surplus Styles is a manufacturer of hair care products,
including shampoos, conditioners, and hair gels. The...
asked 16 minutes ago -
Using an income-expenditure diagram, use the infinite line and
double-drop line tools to show the economy...
asked 24 minutes ago -
Which expression computes a pseudorandom integer between -10 and
10 using rand()
from cstdlib?
A. (rand(...
asked 31 minutes ago -
Roybus, Inc., a manufacturer of flash memory, just reported that
its main production facility in Taiwan...
asked 39 minutes ago -
Two capacitors connected in parallel produce an equivalent
capacitance of 45.0 μF but when connected in...
asked 48 minutes ago -
The differences between the two sets of dependent data are -1,
2,-,2, 2. Round to the...
asked 1 hour ago -
A χ2-curve, looking at the relationship between age and hours
spent working at an office per...
asked 1 hour ago -
The pH of a sample of water from a river is 5.0. A
sample of effluent from...
asked 2 hours ago