vgratian - 1 year ago 52

C++ Question

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 Source

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.