vgratian vgratian - 12 days ago 4
C++ Question

Queue implementation with Linked list in C++

I am trying to implement Queue container in C++ based on a linked list. I used the same structure to implement Stack and it worked fine.

But now I havet trouble with the method "enqueue". I can't understand what exactly is the problem, although I know that pointers are my weak point.

#include <iostream>

template <class N>
class node {
public:
N data;
node* next;
};

template <class Q>
class my_queue {
protected:
node<Q>* m_head;
unsigned int m_size;

public:
my_queue() {
m_head = NULL;
m_size = 0;
}

void enqueue(Q value) {

node<Q>* newel = new node<Q>; // creating the new element
node<Q>* last = m_head; // find the last element in the queue

while(last != NULL) {
last = last->next;
}

newel->data = value;
newel->next = last->next;
last->next = newel;

m_size++;
}

void print() {
node<Q>* element = m_head; // element == each element in the list
while(element != NULL) {
std::cout << element->data << std::endl;
element = element->next;
}
}

};


If I compile this with:

main() {
my_queue<int> q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
q.enqueue(5);
q.print();

return 0;
}


I get no errors, but when I run it I get "Segmentation fault".

Answer

After this loop in the function

while(last != NULL) {
  last = last->next;
}

the pointer last will be always equal to NULL. So the function has undefined behavior due to these statements

newel->next = last->next;
last->next = newel;

The function can be rewritten the following way

void enqueue( const Q &value ) 
{
    node<Q> *newel = new node<Q> { value, nullptr };

    if ( m_head == nullptr )
    {
        m_head = newel;
    }
    else
    {
        node<Q> *last = m_head; // find the last element in the queue

        while ( last->next != nullptr ) last = last->next;

        last->next = newel;
    }

    m_size++;
}

To make the queue more efficient it is better to implement it based on a two-sided list.