you have to implement an unfair queue from the scratch. A skeleton code is provi
ID: 3866984 • 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
Answer for the given Question:
See the below implemetation of unfair queue
#include<iostream>
#include<cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *link;
}*front, *rear;
/*
* Class Declaration
*/
class queue_list
{
public:
void insert(int);
void display();
void del();
queue_list()
{
front = NULL;
rear = NULL;
}
};
/*
* Main: Contains Menu
*/
int main()
{
int choice, item;
queue_list ql;
while (1)
{
cout<<" -------------"<<endl;
cout<<"Operations on Queue"<<endl;
cout<<" -------------"<<endl;
cout<<"1.Insert Element into the Queue"<<endl;
cout<<"2.Delete Element from the Queue"<<endl;
cout<<"3.Traverse the Queue"<<endl;
cout<<"4.Quit"<<endl;
cout<<"Enter your Choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter value to be inserted into the queue: ";
cin>>item;
ql.insert(item);
break;
case 2:
ql.del();
break;
case 3:
ql.display();
break;
case 4:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
/*
* Insert Element into the Queue
*/
void queue_list::insert(int item)
{
node *tmp;
tmp = new (struct node);
tmp->info = item;
tmp->link = NULL;
if (front == NULL)
front = tmp;
else
rear->link = tmp;
rear = tmp;
}
/*
* Delete Element from the Queue
*/
void queue_list::del()
{
node *tmp;
if (front == NULL)
cout<<"Queue Underflow"<<endl;
else
{
tmp = front;
cout<<"Element Deleted: "<<tmp->info<<endl;
front = front->link;
free(tmp);
}
}
/*
* Traversing the Stack
*/
void queue_list::display()
{
node *ptr;
ptr = front;
if (front == NULL)
cout<<"Queue is empty"<<endl;
else
{
cout<<"Queue elements :"<<endl;
while (ptr != NULL)
{
cout<<ptr->info<<" ";
ptr = ptr->link;
}
cout<<endl;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.