Segmentation Fault (core dumped) when trying to run Queue program - C++

Question

I keep getting a Segmentation fault (core dumped) error every time I try to run my code with g++ on Linux. It compiles fine, but then that happens ... All the functions (remove, add and print) seem to have the same problem, I can't seem to figure out what's wrong... Please heeeelppp.

#include <iostream>
#include <string>

using namespace std;

//Create a node struct
struct Node {
  int data;
  Node *next;
  Node *prev;
};

class Queue {
private:
  Node *head;
  Node *tail;
  int size;
public:
  Queue();
  ~Queue();
  void add(int d);
  int remove();
  bool isEmpty();
  void printQueue(bool o);
};


//set to NULL
Queue::Queue() {

  head = tail = NULL;
  size = 0;

}

//destructor
//call remove until empty
Queue::~Queue() {

  while (!isEmpty())
    remove();
}

//adds a node with the given data at the back of the queue
void Queue::add(int d) {

  Node *temp = new Node();
  temp->data = d;
  temp->next = NULL;

  if (isEmpty()) {

    //add to head
    head = temp;

  } else {

    //append
    tail->next = temp;
    tail = temp;

    cout << "Added: " << tail->data << endl;
  }

  size++;
}

//removes the node at the head of the queue and returns its data
int Queue::remove() {

  if (isEmpty()) {

    cout << "The queue is empty." << endl;

  } else {

    Node *temp = new Node;
    temp = head;
    int value = head->data;

    //moves pointer to next node
    head = head->next;

    cout << "Removed: " << head->data << endl;

    size--;
    delete temp;
    return value;

  }
}

//determines if the queue is empty
bool Queue::isEmpty() {
  return (size == 0);
}

//prints the contents of the queue from front to back, or front
//to back, depending on the value of the parameter
void Queue::printQueue(bool o) {

  if (isEmpty()) {

    cout << "The queue is empty." << endl;

  } else {

    Node *p = new Node;

    if (o == true) {

      cout << "Printing in front to back:" << endl;

      //print front to back
      while(p != NULL) {
        p = head;
        cout << p->data << " ";
        p = p->next;
      }

    } else if (o == false) {

      cout << "Printing in back to front:" << endl;

      //print back to front
      while (p != NULL) {
        p = tail;
        cout << p->data << " ";
        p = p->prev;
      }
    }
  }
}

int main() {

  Queue q;

  q.add(8);

  return 0;
}

EDIT: I've made some changes to the code... But I'm still getting the same error. I assume I'm not updating the head and the tail and/or the next and prev nodes correctly... I don't know why it's wrong or what I'm missing, though.

#include <iostream>
#include <string>

using namespace std;

struct Node {
  int data;
  Node *next;
  Node *prev;
};

class Queue {
private:
  Node *head;
  Node *tail;
  int size;
public:
  Queue();
  ~Queue();
  void add(int d);
  int remove();
  bool isEmpty();
  void printQueue(bool o);
};

Queue::Queue() {

  head = tail = NULL;
  size = 0;

}

Queue::~Queue() {

  while (!isEmpty())
    remove();
}

void Queue::add(int d) {

  Node *temp = new Node;
  temp->data = d;
  temp->next = NULL;
  temp->prev = tail;

  if (isEmpty()) {

    //add to head
    head = temp;

  } else {

    //append
    tail->next = temp;
    tail = temp;

    cout << "Added: " << tail->data << endl;
  }
  size++;
}

int Queue::remove() {

  if (isEmpty()) {

    cout << "The queue is empty." << endl;

    return 0;

  } else {

    Node *temp = head;
    int value = head->data;

    cout << "Removed: " << head->data << endl;

    //moves pointer to next node
    head = head->next;
    head->prev = NULL;

    size--;
    delete temp;
    return value;
  }
}

bool Queue::isEmpty() {
  return (size == 0);
}

void Queue::printQueue(bool o) {

  if (isEmpty()) {

    cout << "The queue is empty." << endl;

  } else {

    Node *p;

    if (o == true) {

      p = head;

      cout << "Printing in front to back:" << endl;

      //print front to back
      while(p != NULL) {
        cout << p->data << " ";
        p = p->next;
      }

    } else if (o == false) {

      p = tail;

      cout << "Printing in back to front:" << endl;

      //print back to front
      while (p != NULL) {
        cout << p->data << " ";
        p = p->prev;
      }
    }
  }
}

int main() {

  Queue q;

  q.add(9);
  q.add(10);
  q.add(11);
  q.add(12);
  q.add(13);
  q.add(14);
  q.add(15);
  q.add(16);

  q.remove();
  q.remove();

  q.printQueue(true);
  q.printQueue(false);

  return 0;
}

Unrelated, Insta-Memory Leak: Node *temp = new Node; temp = .... This isn't Java. Related: ` head = head->next;` followed by sending head->data to cout isn't going to end well when head was the last node in queue. head->data dereferences a null pointer, which invokes undefined behavior. — WhozCraig
– WhozCraig, Commented Mar 4, 2015 at 19:58

uesp · Accepted Answer · 2015-03-05 13:26:31Z

Lots of problems:

You have a double-linked Node but never update its prev member in the add/remove methods.
You are keeping track of both the Queue head/tail but don't properly update them when you add/remove nodes.
Both your forward and reverse loops in printQueue() are wrong and result in an infinite loop for any queue with 2 or more elements. Queue output should be just something like:
```
Node *p = head;

while (p != NULL) 
{
    cout << p->data << " ";
    p = p->next;
}
```
Possible null pointer deference in remove() at cout << "Removed: " << head->data << endl; since you've already moved the head pointer by this time. Move the head after the cout.
Memory leak in Queue::remove() at Node *temp = new Node;. Just do Node* temp = head;.
Memory leak in Queue::printQueue() at Node *p = new Node;. You don't need to allocate a node here.
No return value in remove() for an empty queue.

Edit

Don't forget to initialize the tail when adding a node to an empty list:

if (isEmpty()) {
    head = temp;
    tail = temp;
}

To remove a node from the head of a non-empty list it should be something like:

Node *temp = head;
head = head->next;
if (head) head->prev = NULL;
size--;
delete temp;
if (isEmpty()) tail = NULL;

Collectives™ on Stack Overflow

Segmentation Fault (core dumped) when trying to run Queue program - C++

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related