Queue implementation with Linked list in 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".

When you insert the first element, last will be m_head, which was never allocated, so you cannot do last->next = newel. — Polb
– Polb, Commented Nov 27, 2016 at 21:25

Vlad from Moscow · Accepted Answer · 2016-11-27 21:33:56Z

2

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.

edited Nov 27, 2016 at 21:33

answered Nov 27, 2016 at 21:24

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

vgratian Over a year ago

Great, thanks :) Funny, before you added your the revised code, I rewrote it in the exact same way after reading your comment :)

David G Over a year ago

What do you mean by two sided list?

Vlad from Moscow Over a year ago

@0x499602D2 It is a singly-linked list that has the tail pointer. Thus new nodes can be added to any side of the list.

vgratian Over a year ago

My example is a single linked list (each node has only one link to another element, i.e. "next"). A node in a double linked list would have two links: "next" and "previous". See: en.wikipedia.org/wiki/Doubly_linked_list

Vlad from Moscow Over a year ago

@vgratian You could add one more node the tail node to your queue. In this case adding new nodes to the tail of the queue would be much more efficient.

Collectives™ on Stack Overflow

Queue implementation with Linked list in C++

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related