c++data-structuresqueuecircular-queue

Dequeue final node in circular linked list


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

Solution

  • 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();
        }
    }