you have to implement an unfair queue from the scratch. A skeleton code is provi
ID: 3866929 • Letter: Y
Question
you have to implement an unfair queue from the scratch. A skeleton code is provided to guide you through the process. Unfair queue has all the properties of a queue, however, it can do more. you have to implement an unfair queue from the scratch. A skeleton code is provided to guide you through the process. Unfair queue has all the properties of a queue, however, it can do more.
======================================================================
#include <iostream>
#include "queue.h"
int main() {
std::cout << "create a queue with default constructor:"<<std::endl;
ubcse::queue<int> q1;
std::cout << "q1 is created with default constructor"<< std::endl;
if (q1.empty() ) {
std::cout << "Queue is empty ";
} else{
std::cout << "Queue is not empty ";
}
// pushes some values into the queue:
std::cout << "Pushing three values: 10, 20, 30"<< std::endl;
q1.push(10);
q1.push(20);
q1.push(30);
std::cout << "Printing q1: ";
q1.print();
std::cout << "Size of q1: " << q1.size() << std::endl;
std::cout << "poping an item from q1 ..."<< std::endl;
q1.pop();
std::cout << "printing q1 after pop operation:"<< std::endl;
q1.print();
std::cout << "poping rest of the items ..."<< std::endl;
q1.pop();
q1.pop();
std::cout << "Now printing q1 again ..."<< std::endl;
q1.print();
std::cout << "Creating a new queue q2 with default constructor"<< std::endl;
ubcse::queue<int> q2;
q2.push(100);
q2.push(200);
q2.push(300);
std::cout << "printing q2:"<< std::endl;
q2.print();
std::cout << "Perform swap operation."<< std::endl;
q2.swap(q1);
std::cout<< "After swap between q2 and q1:"<<std::endl;
std::cout << "q1 : ";
q1.print();
std::cout << "q2 : ";
q2.print();
std::cout << "Creating another queue with copy constructor:"<< std::endl;
std::cout << "copying q1 to q3"<< std::endl;
ubcse::queue<int> q3(q1);
std::cout << "printing q3:"<< std::endl;
q3.print();
std::cout << "size of q3:";
std::cout << q3.size() << std::endl;
std::cout << "Printing q1:"<< std::endl;
q1.print();
std::cout << "size of q1:";
std::cout << q1.size() << std::endl;
std::cout << "Deleting everything from q3:"<< std::endl;
q3.delete_all();
std::cout << "Printing q3:"<< std::endl;
q3.print();
std::cout << "Printing q1:"<< std::endl;
q1.print();
std::cout << "Pushing values into q1: 400, 500, 600, 700, 800."<< std::endl;
q1.push(400);
q1.push(500);
q1.push(600);
q1.push(700);
q1.push(800);
std::cout << "printing q1:"<< std::endl;
q1.print();
std::cout << "Printing q3:"<< std::endl;
q3.print();
std::cout << "Now removing the 3rd item:"<< std::endl;
q1.delete_from_the_middle(2);
std::cout << "Printing q1 after removing 3rd item :"<< std::endl;
q1.print();
std::cout << "inserting 10000 in the 4th position of q1:"<< std::endl;
q1.insert_in_the_middle(10000, 3);
std::cout << "Printing q1:"<< std::endl;
q1.print();
} //end of main
===============================================================
#ifndef NODE_H_
#define NODE_H_
template <typename ntype>
struct Node {
// Data Fields
/** The data */
ntype data;
/** The pointer to the next node. */
Node* next;
// Constructor
/** Creates a new Node that points to another Node.
@param data_item The data stored
@param next_ptr Pointer to the Node that is
pointed to by the new Node
*/
Node(const ntype& data_item, Node* next_ptr = nullptr) :
data(data_item), next(next_ptr) {}
};
#endif
===============================================
#ifndef QUEUE_CPP_
#define QUEUE_CPP_
/* ************** GETTER FUNCTIONS *************************/
/**
* TO DO: implement get_head method.
* This method returns the head pointer.
*/
template <typename dtype>
Node<dtype>* queue<dtype>::get_head() const{
//write your code here...
} // end of get_head function.
/**
* TO DO: implement get_tail method.
* This method returns the tail pointer.
*/
template <typename dtype>
Node<dtype>* queue<dtype>::get_tail() const{
//write your code here ...
} // end of get_tail function.
/**
* TO DO: implement size method.
* This function returns the size of the queue.
* return type is 'size_t'.
*/
template <typename dtype>
size_t queue<dtype>::size() const{
//write your code here...
} /* end of size method */
/**
* TO DO : implement empty method.
* This function returns whether the queue is empty
* or not. if empty it returns true, otherwise returns
* false.
*/
template <typename dtype>
bool queue<dtype>::empty() const {
// write your code here ....
}
/************ SETTER FUNCTIONS ***********************/
/**
* TO DO : implement set_head method.
* This function updates the head pointer
* with given pointer.
*/
template <typename dtype>
void queue<dtype>::set_head(Node<dtype>* val){
//write your code here ...
}
/**
* TO DO : implement set_tail method.
* This function updates the tail pointer
* with given pointer.
*/
template <typename dtype>
void queue<dtype>::set_tail(Node<dtype>* val){
//write your code here ...
}
/**
* TO DO: implement set_size.
* This method can update the num_items with the given
* input.
*/
template <typename dtype>
void queue<dtype>::set_size(size_t n_items){
//write your code here ...
}
/************ CORE QUEUE OPERATIONS **********************/
/** TO DO:
* This method addes the given item onto the back
* of the queue. Update the tail pointer accordingly.
* and also increase 'num_items' by 1.
*/
template <typename dtype>
void queue<dtype>::push(const dtype& val){
//write your code here ...
} // end of push function
/**
* TO DO: implement pop method.
* This function removes the item from the front of the queue.
* it returns nothing.
* if queue is empty it will print a message "queue is empty"
* and return.
* Don't forget to reduce the 'num_items' by 1.
*/
template <typename dtype>
void queue<dtype>::pop(){
//write your code here ...
} /* end of pop method */
/**
* TO DO: implement front method.
* This function returns the front of the queue.
* if the queue is empty is prints a message "queue is empty"
* throw an error.
*/
template <typename dtype>
const dtype& queue<dtype>::front() const{
//write your code here ...
}
/**
* TO DO: implement front method.
* This function returns the front of the queue.
* if the queue is empty is prints a message "queue is empty"
* throw an error.
*/
template <typename dtype>
dtype& queue<dtype>::front(){
//write your code here ...
}
/************ FOR PORTABILITY **********************************/
/**
* TO DO : implement swap method.
* Input argument:
* @param other - reference to a queue.
* exchange contents of this queue by those of 'other'.
* also swap the 'num_items'.
*/
template <typename dtype>
void queue<dtype>::swap(queue<dtype>& other){
//write your code here ...
} /* end of swap method */
/******* UNFAIR QUEUE OPERATIONS **********************************/
/**
* TO DO: implement inset_in_the_middle
* This method enables the queue to be unfair. With this function
* you can push something in the middle of the queue. As argument
* you need two arguments - the value that you want to push and
* the position where you want to push. position argument is similar
* to index, it starts from 0. That means, the front of the queue has
* position 0.
*/
template <typename dtype>
void queue<dtype>::insert_in_the_middle(const dtype& val, const size_t position){
//write your code here ...
}
/** TO DO:
* Implement delete_from_the_middle
* This method also enables the queue to be unfair. You can remove something
* from the middle of the queue. As input argument you need the position that
* you want to delete. position argument is similar
* to index, it starts from 0. That means, the front of the queue has
* position 0.
*/
template <typename dtype>
void queue<dtype>::delete_from_the_middle(size_t position){
//write your code here ...
}
/**
* This method deletes all the elements in the queue
* without memory leak.
*/
template <typename dtype>
void queue<dtype>::delete_all(){
//write your code here ...
} /* end of delete_all */
/******************** PRINT *************************************/
/**
* This method prints the queue.
* if the queue is empty, it prints error message
*/
template <typename dtype>
void queue<dtype>::print(){
if (num_items == 0 ){
std::cout << "Queue is empty"<< std::endl;
}
else{
Node<dtype>* iter = head;
//std::cout<<"here "<< head->next->data<<std::endl;
while( iter != nullptr ){
std::cout << iter->data << " ";
iter = iter->next;
}
std::cout << std::endl;
}
} /* end of print method */
#endif
===============================================
#ifndef QUEUE_H_
#define QUEUE_H_
#include <string>
namespace ubcse{
#include "node.h"
template <typename dtype>
class queue {
private:
Node<dtype>* head;
Node<dtype>* tail;
size_t num_items;
public:
/** TO DO: implement default constructor.
* default constructor:
* this constructor initializes the following:
* head to nullptr,
* tail to nullptr,
* num_item to zero.
*/
queue<dtype>(){
// write your code here
};
/** TO DO: implement copy constructor.
* copy constructor:
* This constructor performs deep copy of the queue.
* Input argument for this constructor is a constant
* reference of another queue. You cannot change the
* given queue.
* Copy all the data members from the given queue to
* this queue. That means both num_items and queue. Both 'head'
* 'tail' pointer should point properly in this queue.
* Don't forget to copy num_itmes as well.
*/
queue<dtype>(queue<dtype>& other){
num_items = other.size();
if (num_items == 0){
head = nullptr;
tail = nullptr;
}
else{
// write your code here.
}
};
/** TO DO: implement destructor.
* Write a destructor to release memory.
*/
// write your code here.
/******* getter function declarations *******************/
/* returns the head pointer */
Node<dtype>* get_head() const;
/* returns the tail pointer. */
Node<dtype>* get_tail() const;
/* returns the size of the queue. */
size_t size() const;
/* checks whether queue is empty or not. */
bool empty() const;
/******** setter/ modifier function declarations *************/
/* assign the given pointer val to head pointer */
void set_head(Node<dtype>* val);
/* assign the given pointer val to tail pointer */
void set_tail(Node<dtype>* val);
/* update the current number of items in the queue */
void set_size(size_t n_items);
/********************* Core queue operations **********/
/* pushes an item onto the tail. */
void push(const dtype& val);
/* removes the front item from the queue */
void pop();
/* return the front element, however, it is not going
to delete the front element. */
dtype& front();
const dtype& front() const;
/******** For portability **********************/
/* performs swap between two queues */
void swap(queue<dtype>& other);
/********* operations for unfair queue **************/
/* deletes the whole queue without memory leak */
void delete_all();
/* delete data from the middle */
void delete_from_the_middle(size_t position);
/* insert data in the middle */
void insert_in_the_middle(const dtype& val, const size_t position);
/******* printing *******************************/
/* prints the whole queue */
void print();
}; // end of Stack class
#include "queue.cpp"
} // end of namespace ubcse
#endif
Explanation / Answer
queue.h and queue.cpp have been completed and given below. Output of main is shown below. Please don't forget to rate the answer if it helped. Thank you.
queue.h
#ifndef QUEUE_H_
#define QUEUE_H_
#include <string>
namespace ubcse{
#include "node.h"
template <typename dtype>
class queue {
private:
Node<dtype>* head;
Node<dtype>* tail;
size_t num_items;
public:
/** TO DO: implement default constructor.
* default constructor:
* this constructor initializes the following:
* head to nullptr,
* tail to nullptr,
* num_item to zero.
*/
queue<dtype>(){
head = nullptr;
tail = nullptr;
num_items = 0;
};
/** TO DO: implement copy constructor.
* copy constructor:
* This constructor performs deep copy of the queue.
* Input argument for this constructor is a constant
* reference of another queue. You cannot change the
* given queue.
* Copy all the data members from the given queue to
* this queue. That means both num_items and queue. Both 'head'
* 'tail' pointer should point properly in this queue.
* Don't forget to copy num_itmes as well.
*/
queue<dtype>(queue<dtype>& other){
num_items = other.size();
if (num_items == 0){
head = nullptr;
tail = nullptr;
}
else{
num_items = 0;
Node<dtype> *curr = other.get_head();
while(curr != nullptr)
{
push(curr->data);
curr = curr->next;
}
}
};
/** TO DO: implement destructor.
* Write a destructor to release memory.
*/
// write your code here.
~queue<dtype>()
{
delete_all();
}
/******* getter function declarations *******************/
/* returns the head pointer */
Node<dtype>* get_head() const;
/* returns the tail pointer. */
Node<dtype>* get_tail() const;
/* returns the size of the queue. */
size_t size() const;
/* checks whether queue is empty or not. */
bool empty() const;
/******** setter/ modifier function declarations *************/
/* assign the given pointer val to head pointer */
void set_head(Node<dtype>* val);
/* assign the given pointer val to tail pointer */
void set_tail(Node<dtype>* val);
/* update the current number of items in the queue */
void set_size(size_t n_items);
/********************* Core queue operations **********/
/* pushes an item onto the tail. */
void push(const dtype& val);
/* removes the front item from the queue */
void pop();
/* return the front element, however, it is not going
to delete the front element. */
dtype& front();
const dtype& front() const;
/******** For portability **********************/
/* performs swap between two queues */
void swap(queue<dtype>& other);
/********* operations for unfair queue **************/
/* deletes the whole queue without memory leak */
void delete_all();
/* delete data from the middle */
void delete_from_the_middle(size_t position);
/* insert data in the middle */
void insert_in_the_middle(const dtype& val, const size_t position);
/******* printing *******************************/
/* prints the whole queue */
void print();
}; // end of Stack class
#include "queue.cpp"
} // end of namespace ubcse
#endif
queue.cpp
#ifndef QUEUE_CPP_
#define QUEUE_CPP_
#include "queue.h"
#include <iostream>
using namespace ubcse;
/* ************** GETTER FUNCTIONS *************************/
/**
* TO DO: implement get_head method.
* This method returns the head pointer.
*/
template <typename dtype>
Node<dtype>* queue<dtype>::get_head() const{
return head;
} // end of get_head function.
/**
* TO DO: implement get_tail method.
* This method returns the tail pointer.
*/
template <typename dtype>
Node<dtype>* queue<dtype>::get_tail() const{
return tail;
} // end of get_tail function.
/**
* TO DO: implement size method.
* This function returns the size of the queue.
* return type is 'size_t'.
*/
template <typename dtype>
size_t queue<dtype>::size() const{
return num_items;
} /* end of size method */
/**
* TO DO : implement empty method.
* This function returns whether the queue is empty
* or not. if empty it returns true, otherwise returns
* false.
*/
template <typename dtype>
bool queue<dtype>::empty() const {
if(size() == 0 )
return true;
else
return false;
}
/************ SETTER FUNCTIONS ***********************/
/**
* TO DO : implement set_head method.
* This function updates the head pointer
* with given pointer.
*/
template <typename dtype>
void queue<dtype>::set_head(Node<dtype>* val){
head = val;
}
/**
* TO DO : implement set_tail method.
* This function updates the tail pointer
* with given pointer.
*/
template <typename dtype>
void queue<dtype>::set_tail(Node<dtype>* val){
tail = val;
}
/**
* TO DO: implement set_size.
* This method can update the num_items with the given
* input.
*/
template <typename dtype>
void queue<dtype>::set_size(size_t n_items){
num_items = n_items;
}
/************ CORE QUEUE OPERATIONS **********************/
/** TO DO:
* This method addes the given item onto the back
* of the queue. Update the tail pointer accordingly.
* and also increase 'num_items' by 1.
*/
template <typename dtype>
void queue<dtype>::push(const dtype& val){
Node<dtype> *newNode = new Node<dtype>(val, nullptr);
if(empty())
{
head = tail = newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
num_items++;
} // end of push function
/**
* TO DO: implement pop method.
* This function removes the item from the front of the queue.
* it returns nothing.
* if queue is empty it will print a message "queue is empty"
* and return.
* Don't forget to reduce the 'num_items' by 1.
*/
template <typename dtype>
void queue<dtype>::pop(){
if(empty())
return;
Node<dtype> *nextNode = head->next;
delete head;
head = nextNode;
if(head == nullptr)
tail = nullptr;
num_items--;
} /* end of pop method */
/**
* TO DO: implement front method.
* This function returns the front of the queue.
* if the queue is empty is prints a message "queue is empty"
* throw an error.
*/
template <typename dtype>
const dtype& queue<dtype>::front() const{
if(empty())
{
std::cout << "queue is empty" << std::endl;
throw "queue is empty";
}
return head->data;
}
/**
* TO DO: implement front method.
* This function returns the front of the queue.
* if the queue is empty is prints a message "queue is empty"
* throw an error.
*/
template <typename dtype>
dtype& queue<dtype>::front(){
if(empty())
{
std::cout << "queue is empty" << std::endl;
throw "queue is empty";
}
return head->data;
}
/************ FOR PORTABILITY **********************************/
/**
* TO DO : implement swap method.
* Input argument:
* @param other - reference to a queue.
* exchange contents of this queue by those of 'other'.
* also swap the 'num_items'.
*/
template <typename dtype>
void queue<dtype>::swap(queue<dtype>& other){
//swap the head nodes
Node<dtype> *tempNode = head;
head = other.get_head();
other.head = tempNode;
//swap the tail nodes
tempNode = tail;
tail = other.tail;
other.tail = tempNode;
//swap the sizes
int tempSize = num_items;
num_items = other.num_items;
other.num_items = tempSize;
} /* end of swap method */
/******* UNFAIR QUEUE OPERATIONS **********************************/
/**
* TO DO: implement inset_in_the_middle
* This method enables the queue to be unfair. With this function
* you can push something in the middle of the queue. As argument
* you need two arguments - the value that you want to push and
* the position where you want to push. position argument is similar
* to index, it starts from 0. That means, the front of the queue has
* position 0.
*/
template <typename dtype>
void queue<dtype>::insert_in_the_middle(const dtype& val, const size_t position){
//check if the position is within valid range
if(position <0 || position >= num_items)
return;
Node<dtype> *curr = head;
Node<dtype> *prev = nullptr;
int index = 0;
while(index < position)
{
prev = curr;
curr = curr->next;
index++;
}
Node<dtype> *newNode = new Node<dtype>(val);
if(prev == nullptr) //insertion before head
{
newNode->next = head;
head = newNode;
if(tail == nullptr) //the list was empty
tail = head;
}
else
{
prev->next = newNode;
newNode->next = curr;
}
num_items++;
}
/** TO DO:
* Implement delete_from_the_middle
* This method also enables the queue to be unfair. You can remove something
* from the middle of the queue. As input argument you need the position that
* you want to delete. position argument is similar
* to index, it starts from 0. That means, the front of the queue has
* position 0.
*/
template <typename dtype>
void queue<dtype>::delete_from_the_middle(size_t position){
//check if the position is within valid range
if(position < 0 || position >= num_items)
return;
int index = 0;
Node<dtype> *curr = head;
Node<dtype> *prev = nullptr;
while(index < position)
{
prev = curr;
curr = curr->next;
index++;
}
if(prev == nullptr) //deleting head
{
head = head->next;
if(head == nullptr) //now list is empty
tail = nullptr;
}
else
{
prev->next = curr->next;
}
delete curr;
num_items--;
}
/**
* This method deletes all the elements in the queue
* without memory leak.
*/
template <typename dtype>
void queue<dtype>::delete_all(){
//write your code here ...
Node<dtype> *curr = head;
Node<dtype> *nextNode;
while(curr != nullptr)
{
nextNode = curr->next;
delete curr;
curr = nextNode;
}
head = tail = nullptr;
num_items = 0;
} /* end of delete_all */
/******************** PRINT *************************************/
/**
* This method prints the queue.
* if the queue is empty, it prints error message
*/
template <typename dtype>
void queue<dtype>::print(){
if (num_items == 0 ){
std::cout << "Queue is empty"<< std::endl;
}
else{
Node<dtype>* iter = head;
//std::cout<<"here "<< head->next->data<<std::endl;
while( iter != nullptr ){
std::cout << iter->data << " ";
iter = iter->next;
}
std::cout << std::endl;
}
} /* end of print method */
#endif
output
create a queue with default constructor:
q1 is created with default constructor
Queue is empty
Pushing three values: 10, 20, 30
Printing q1:
10 20 30
Size of q1: 3
poping an item from q1 ...
printing q1 after pop operation:
20 30
poping rest of the items ...
Now printing q1 again ...
Queue is empty
Creating a new queue q2 with default constructor
printing q2:
100 200 300
Perform swap operation.
After swap between q2 and q1:
q1 : 100 200 300
q2 : Queue is empty
Creating another queue with copy constructor:
copying q1 to q3
printing q3:
100 200 300
size of q3:3
Printing q1:
100 200 300
size of q1:3
Deleting everything from q3:
Printing q3:
Queue is empty
Printing q1:
100 200 300
Pushing values into q1: 400, 500, 600, 700, 800.
printing q1:
100 200 300 400 500 600 700 800
Printing q3:
Queue is empty
Now removing the 3rd item:
Printing q1 after removing 3rd item :
100 200 400 500 600 700 800
inserting 10000 in the 4th position of q1:
Printing q1:
100 200 400 10000 500 600 700 800
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.