4
\$\begingroup\$

In my intro CS class we're reviewing data structures. I'm currently working on implementing a queue using a linked list (FIFO) in C. I'd appreciate a review of the implementation as well as of my understanding of how a queue should work

// This program is implementation of queue data structure
// via linked list (FIFO)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    int number;
    struct node *next;
} node;


node *enqueue(int element, node *temp);
node *dequeue(int n, node *temp);
void display(node *temp);
void destroy_queue(node *temp);

int main()
{
    node *queue = NULL;

    // add some elements to queue
    for (int i = 0; i < 5; i++)
    {
        queue = enqueue((i + 1), queue);
    }


    // display queue
    display(queue);

    // dequeue 2 elements from queue
    printf("Removing two elements from queue...\n");
    queue = dequeue(2, queue);

    //display queue
    display(queue);

    // free memory
    destroy_queue(queue);

}

node *enqueue(int element, node *temp)
{
    node *newElement = malloc(sizeof(node));
    node *head = temp;
    if (newElement == NULL)
    {
        fprintf(stderr, "No memory for the new queue element");
        return temp;
    }

    newElement->number = element;
    newElement->next = NULL;

    if (head == NULL)
    {
        return newElement;
    }
    else
    {
        while ((temp->next) != NULL)
        {
            temp = temp->next;
        }
        temp->next = newElement;
    }
    return head;
}

node *dequeue(int n, node *temp)
{
    node *aux;
    for (int i = 0; i < n; i++)
    {
        if (!temp)
        {
            fprintf(stderr,"No elements to remove!");
            return temp;
        }
        aux = temp->next;
        free(temp);
        temp = aux;
    }
    return temp;
}

void display(node *temp)
{
    while (temp)
    {
        printf("Elements in queue are: %i\n", temp->number);
        temp = temp->next;
    }
}

void destroy_queue(node *temp)
{
    node *aux = temp;
    while (temp)
    {
        aux = temp->next;
        free(temp);
        temp = aux;
    }
}
\$\endgroup\$
4
\$\begingroup\$
  • Having a separate queue structure

    typedef struct {
        node * head;
        node * tail;
    } queue;
    

    will bring you several benefits:

    • Most important, enqueue would take a constant time (vs linear in queue length you have now).

    • The client would be relieved from responsibility to maintain the head node.

    • enqueue doesn't inform the client that it failed the allocation. fprintf is good for the human, but does nothing for the calling routine. Having the queue structure enables you to return an error code.

  • The specialized utility functions, like enqueue and dequeue should not print anything. They must communicate success/error to the caller, and let it act appropriately.

  • else in enqueue is redundant.

  • I don't see why do you #include <string.h>.
\$\endgroup\$
  • \$\begingroup\$ Constant time enqueue() and dequeue() does not require 2 pointers in queue. One is sufficient. Simple have member .tail and let the tail of the queue point to the head. Adding to either end of queue is O(1) Removing from the head is also O(1). \$\endgroup\$ – chux Oct 11 '18 at 5:30
  • 1
    \$\begingroup\$ @chux Right. Circular queue is better. I was pondering that as well, but decided against for purely didactical reasons. \$\endgroup\$ – vnp Oct 11 '18 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.