When I am trying to dequeue the final node in a circular linked list based queue in C++ I am getting a segmentation fault. The rest of the elements before the final one are removed successfully, its just the last one and it seems to be an issue with deallocation however the only log from terminal is Segmentation fault: 11. Could someone help me understand why I am getting this behavior. I've pasted the complete implementation file below incase it is a problem with the Enqueue function or constructors.
#include "BQUEUE.h"
#include <iostream>
using namespace std;
BQUEUE::BQUEUE(): front(nullptr) {}
BQUEUE::BQUEUE(const BQUEUE & queue){
bqnode *temp = queue.front;
while (temp->next != queue.front){
Enqueue(temp->time);
temp = temp->next;
}
Enqueue(temp->time);
}
BQUEUE::~BQUEUE(){
bqnode *current = front;
while (current->next != front)
Dequeue();
}
void BQUEUE::Dequeue(){
// Empty queue
if (front == nullptr){
return;
} else if (front->next == front){
front->next = nullptr;
delete front;
front = nullptr;
} else {
bqnode *temp = front, *current = front;
while (current->next != front)
current = current->next;
front = front->next;
current->next = front;
delete temp;
}
}
void BQUEUE::Print(){
bqnode *temp = front;
while (temp->next != front){
cout << temp->time << endl;
temp = temp->next;
}
cout << temp->time << endl;
}
void BQUEUE::Enqueue(int i){
bqnode *newNode = new bqnode;
newNode->time = i;
if (front == nullptr){
front = newNode;
front->next = front;
} else {
newNode->next = front;
bqnode *previous = front;
if (previous->next == front){
front->next = newNode;
return;
}
while (previous->next != front)
previous = previous->next;
previous->next = newNode;
}
}
DRIVER:
#include <iostream>
#include "BQUEUE.h"
using namespace std;
int main(){
BQUEUE k;
k.Enqueue(60);
k.Dequeue(); // Segmentation fault occurs here
}
HEADER:
#ifndef BQUEUE_H
#define BQUEUE_H
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;
};
#endif
One issue is this:
void BQUEUE::Dequeue() {
// Empty queue
if (front == nullptr) {
return;
}
else if (front->next == front) { // <-- This is invoked when there is only one node remaining
front->next = nullptr;
delete front;
front = nullptr; // <--- This is now nullptr
}
...
Then in the destructor, you didn't check if the front
is nullptr
:
BQUEUE::~BQUEUE() {
bqnode *current = front; // <-- No check to see if front is nullptr
while (current->next != front)
Dequeue();
}
You then access current->next
, which is invalid since current
is nullptr
. The fix is to simply check if front
is nullptr
, and if it is, there is nothing to do.
BQUEUE::~BQUEUE() {
if ( front )
{
bqnode *current = front;
while (current->next != front)
Dequeue();
}
}