Linked List Enqueue and Dequeue

Question

I'm having a little trouble with my enqueue and dequeue for a linked list implemented queue using c++. My teacher says templates are off limits and I cannot change the public and private functions, as he gave them to us. I keep getting a segmentation fault. I don't really understand what I am doing wrong. I've included the header and the enqueue and dequeue functions as well.

Header

const int MAX_STRING = 6;

typedef char Element300[MAX_STRING + 1];

class Queue300
{

    public:
        Queue300();
        Queue300(Queue300&);
        ~Queue300();
        void enQueue300(const Element300);
        void deQueue300(Element300);
        void view300();

    private:
        struct Node300;
        typedef Node300 * NodePtr300;
        struct Node300
        {
            Element300 element;
            NodePtr300 next;
        };
        NodePtr300 front, rear;
};

EnQueue

void Queue300::enQueue300(const Element300 input)


{
    NodePtr300 temp = NULL;

    temp = new (std::nothrow) Node300;

    if (temp == NULL)
    {
        cerr << "The queue is full, could not add(enqueue) any more elements." << endl;
    }

    else if (front == NULL && rear == NULL)
    {
        strcpy(temp->element, input);
        rear = temp;
        rear->next = NULL;
        front = rear;
        temp = NULL;
    }

    else
    {
        strcpy(temp->element, input);
        temp = rear->next;
        rear = temp;
        rear->next = NULL;
        temp = NULL;
    }
}

Dequeue

void Queue300::deQueue300(Element300 input)



{
    NodePtr300 temp = NULL;

    if (rear == NULL && front == NULL)
    {
        cerr << "The queue is already empty, could not delete(dequeue) any more elements." << endl;
    }

    else if (front == rear)
    {
        strcpy(temp->element, input);
        temp = front;
        delete temp;
        temp = NULL;
        front = NULL;
        rear = NULL;
    }

    else
    {
        strcpy(temp->element, input);
        temp = front;
        front = front->next;
        temp->next = NULL;
        delete temp;
        temp = NULL;
    }
}

Answer 1

In enqueue, when you say "temp = rear->next", you overwrite the pointer to your new node in temp.

When adding new nodes into a linked list, it's usually best to set up the pointers in the new node first:

temp->next = null;
rear->next = temp;
rear=temp;

Also:

• after reporting an error, you have to return. if you just carry on you will crash. It's better to throw an exception or return an error code

• the strcpys in dequeue go the wrong way

• to prevent buffer overrun, you should really use strncpy instead of strcpy and then make sure the destination is null-terminated since Element is supposed to be a string

Answer 2

Let's take a look at Enqueue:

    if (temp == NULL)
    {
        ...
    }
    else if (front == NULL && rear == NULL)
    {
        ...
    }
    else
    {
        strcpy(temp->element, input); // copy input into temp->element

        // temp points to rear->next (it is always NULL, isn't it?)
        // we lost the Node300 previously pointed by temp.
        temp = rear->next; 

        // rear points to the same location as temp (NULL)
        rear = temp;

        // rear->next: dereferencing NULL /!\
        rear->next = NULL;

        temp = NULL;
    }

Time for ASCII art. This is before enqueue:

  REAR -------------------
                         |
                         v
          [0]--> ... -->[N]-->NULL
           ^
  FRONT ---|

You allocate a node [X], referenced by temp:

temp --> [X]

REAR's next must point to the same node:

REAR
 |   
 v
[N] --> [X]
         ^
         |
        temp

Then, REAR must be updated to reference [X]. You don't even need a temp pointer as far as pointer manipulations are concerned, but let's keep it because you are checking if the node is properly allocated before, which is nice to have.

rear->next = temp;
rear = temp;       // or rear = rear->next;
temp->next = NULL; // or rear->next = NULL;

Note also that you perform strcpy(temp->element, input); in both else branches. You could return from the function when temp == NULL and do the copy before checking if both front and rear are NULL.