I have a code of a doubly linked circular queue where you are to use one pointer
ID: 3681296 • Letter: I
Question
I have a code of a doubly linked circular queue where you are to use one pointer to the front, add (enqueue) to the back and delete (dequeue) from the front. It works fine in theory, however, I'm skeptical that it is actually doing the opposite, adding to the front and taking away from the back. Can someone explain how exactly the code works? Maybe a diagram of the linked list? Or, if it is not working as instructed, how would I fix it? I am going to attach the instructions to the assignment and then the code below.
Instructions:
After completing this assignment you will be able to do the following:
(1) manipulate pointers, (2) allocate memory dynamically, (3) implement a default constructor, copy constructor and destructor, (4) use only one pointer to add to the back and to dequeue from the front of the queue.
Header file:
class bqnode
{
public:
int time;
bqnode *prev, *next;
};
class BQUEUE
{
public:
BQUEUE( );
~BQUEUE( );
BQUEUE(const BQUEUE &);
void Enqueue(int);
void Dequeue( );
void Print( );
private:
bqnode *front;//use ONLY one pointer
};
.CPP file:
#include "BQUEUE.h"
#include<iostream>
using namespace std;
/**********************************************************************************************
Name: BQUEUE
Precondition: The state of the object (private data) has not been initialized
Postcondition: The state has been initialized to the default values described below
Description: This is the default constructor which will be called automatically when
an object is declared. It will initialize the state of the class.
***********************************************************************************************/
BQUEUE::BQUEUE()
{
front = new bqnode; //front node
front->next = NULL;
front->prev = NULL;
front->time = -1; //set front pointer time to flag value
}
/**********************************************************************************************
Name: ~BQUEUE
Precondition: The state of the object (private data) has been initialized
Postcondition: Memory is de-allocated
Description: This is the destructor which de-allocates memory and "deletes" the circular queued list
***********************************************************************************************/
BQUEUE::~BQUEUE()
{
while (front->time != -1) //while loop to delete
{
delete front; //delete
front = front->next; //front now points next and we repeat
}
}
/**********************************************************************************************
Name: BQUEUE
Precondition: The state of the object (private data) has not been initialized
Postcondition: The state has been initialized to the values of the explicit object
Description: This is the copy constructor which will create an identical circular queue of the
explicit argument and copy it to the implicit argument.
***********************************************************************************************/
BQUEUE::BQUEUE(const BQUEUE &org)
{
front = org.front; //implicit front now = explicit front...
}
/**********************************************************************************************
Name: Enqueue
Precondition: The state of the object (private data) has been initialized
Postcondition: An integer has been added to the queue
Description: This function, enqueue, inserts an integer into the queue.
***********************************************************************************************/
void BQUEUE::Enqueue(int orgTime)
{
bqnode *newNode = new bqnode; //new node
newNode->time = orgTime; //time = int passed
bqnode *temp = new bqnode; //temp...
temp = front;
if (front->next == NULL) //if front->next is null, the list is empty...
{
newNode->next = front; //make first node
newNode->prev = temp;
temp->next = newNode;
front->prev = newNode;
}
else //else means queue has at least one element...
{
while (temp->next->time != -1) //add to the end of the queue
{
temp = temp->next;
}
newNode->next = front;
newNode->prev = temp;
temp->next = newNode;
front->prev = newNode;
}
cout << orgTime << " has been enqueued." << endl;
}
/**********************************************************************************************
Name: Dequeue
Precondition: The state of the object (private data) has been initialized
Postcondition: An integer is removed from the queue
Description: This function, Dequeue, takes an integer out of the queue.
***********************************************************************************************/
void BQUEUE::Dequeue()
{
if (front->next->time != -1) //if true, there is at least one element in the queue...
{
cout << front->next->time //cout statement
<< " has been dequeued." << endl;
front->next = front->next->next; //next points next
front->next->prev = front; //previous unlinked
}
else
cout << "Error, queue is empty!" << endl; //error message (empty)
}
/**********************************************************************************************
Name: Print
Precondition: The state of the object (private data) has been initialized
Postcondition: The queue is displayed in the output.
Description: This function, Print, displays all integers within the queue.
***********************************************************************************************/
void BQUEUE::Print()
{
bqnode *temp = new bqnode; //temp node
temp = front;
if (temp->next == NULL) //checks if empty
{
cout << "Error, queue is empty!" << endl; //error message (empty)
}
else
{
cout << "Time in queues include: " << endl; //cout statement
while (temp->next->time != -1) //while !empty
{
cout << " " << temp->next->time << endl; //print time
temp = temp->next; //temp node point next
}
}
}
Explanation / Answer
#include "BQUEUE.h"
#include<iostream>
using namespace std;
// add a constructor to bqnode for node creation
// which initializes its next and prvs pointers
bqnode::bqnode() {
prvs = next = this;
}
/**********************************************************************************************
Name: BQUEUE
Precondition: The state of the object (private data) has not been initialized
Postcondition: The state has been initialized to the default values described below
Description: This is the default constructor which will be called automatically when
an object is declared. It will initialize the state of the class.
***********************************************************************************************/
BQUEUE::BQUEUE() {
// set it to null instead of creating an empty node
// there is no need
front = NULL;
}
/**********************************************************************************************
Name: ~BQUEUE
Precondition: The state of the object (private data) has been initialized
Postcondition: Memory is de-allocated
Description: This is the destructor which de-allocates memory and "deletes" the circular queued list
***********************************************************************************************/
BQUEUE::~BQUEUE() {
// it is better to use do while loop when dealing with
// doubly linked lists because pointers do not refer to NULL
// check if list is already NULL
while (front->next != front) {
// connect prvs node to next
front->prvs->next = front->next;
// connect next to prvs
front->next->prvs = front->next;
// store new front
bqnode* new_front = front->next;
// free the memory for current node
delete front;
// update to new front
front = new_front;
}
// delete only node
delete front;
// set pointer to null
front = NULL;
}
/**********************************************************************************************
Name: BQUEUE
Precondition: The state of the object (private data) has not been initialized
Postcondition: The state has been initialized to the values of the explicit object
Description: This is the copy constructor which will create an identical circular queue of the
explicit argument and copy it to the implicit argument.
***********************************************************************************************/
BQUEUE::BQUEUE(const BQUEUE &org)
{
front = org.front; //implicit front now = explicit front...
}
/**********************************************************************************************
Name: Enqueue
Precondition: The state of the object (private data) has been initialized
Postcondition: An integer has been added to the queue
Description: This function, enqueue, inserts an integer into the queue.
***********************************************************************************************/
void BQUEUE::Enqueue(int orgTime) {
// new node for new data
bqnode* new_node = new bqnode();
new_node->time = orgTime;
// if already empty queue
if (front == NULL) {
front = new_node;
} else {
// connect new node to old front node
new_node->next = front;
// connect new node to prvs of old front node
new_node->prvs = front->prvs;
// connect old front node to new node
front->prvs = new_node;
// update the front to new node
front = new_node;
}
}
/**********************************************************************************************
Name: Dequeue
Precondition: The state of the object (private data) has been initialized
Postcondition: An integer is removed from the queue
Description: This function, Dequeue, takes an integer out of the queue.
***********************************************************************************************/
void BQUEUE::Dequeue() {
// if nothing to dequeue
if (front == NULL) return;
// check if it is the only node
if (front->prvs == front) {
// output deleted content
cout << front->time << " has been dequed!" << endl;
// free memory and make pointer NULL
delete front;
front = NULL;
} else {
bqnode* prvs_node = front->prvs;
// set last nodes next pointer as front
front->prvs->prvs->next = front;
// set first pointers last node as last but one
front->prvs = front->prvs->prvs;
// output dequed content
cout << prvs_node->time << " has been dequed!" << endl;
// free memory and set it to NULL
delete prvs_node;
prvs_node = NULL;
}
}
/**********************************************************************************************
Name: Print
Precondition: The state of the object (private data) has been initialized
Postcondition: The queue is displayed in the output.
Description: This function, Print, displays all integers within the queue.
***********************************************************************************************/
void BQUEUE::Print()
{
bqnode *temp = new bqnode; //temp node
temp = front;
if (temp->next == NULL) //checks if empty
{
cout << "Error, queue is empty!" << endl; //error message (empty)
}
else
{
cout << "Time in queues include: " << endl; //cout statement
while (temp->next->time != -1) //while !empty
{
cout << " " << temp->next->time << endl; //print time
temp = temp->next; //temp node point next
}
}
}
I have updated code. But node tested.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.