Thread: Need Tips - My Queue Implementation

  1. #1
    Registered User
    Join Date
    Sep 2018
    Posts
    208

    Need Tips - My Queue Implementation

    I've implemented a Queue Data Structure which stores struct Coordinate data elements.

    struct Queue is the structure which stores the queue.
    -> It has a size to represent the queue's size
    (is it a better idea for the size to be an int?)
    -> queue_node are nodes of a linked list, which contain two members: data element, and a pointer to the next element.
    -> It has two members front and back which point to the beginning and end of the queue.

    => Could I have represented the Queue in a different way? I intially thought about using an array, but I realized that it is not possible to shave off a specific amount of bytes from the front.

    queue_initialize is called in the declaration of the struct Queue to initialize the queue.
    => Is it perhaps possible to ensure that queue_initialize is always used in the declaration of a struct Queue?

    queue_push and queue_pop push elements to the front of the queue and pop elements from the back of the queue.

    I don't know what to do when malloc() fails. I wrote a function check_malloc_fail() which is supposed to be called with the pointer which is pointing to newly allocated memory. I just made it print to stderr and exit the program if malloc failed.


    Any tips, including tips on how to name things, how to space things, perhaps modularize a bit more (eg. maybe I should write a function that allocates memory and checks whether malloc failed and use that instead, ensuring malloc is always tested when memory is allocated), or any other tips, are appreciated.

    code:

    Code:
    struct Coordinate {
        int x;
        int y;
    };
    
    
    void check_malloc_fail(void* input_ptr) {
       
       if (input_ptr == NULL) {
          fprintf(stderr, "malloc failed\n");
          exit(EXIT_FAILURE);
       }
    }
    
    
    struct Queue {
    
    
       struct queue_node {
    
    
          struct queue_node* next_node;
          struct Coordinate data;
    
    
       } *back, *front;
    
    
       size_t size;
    };
    
    
    struct Queue queue_initialize(void) {
       return (struct Queue) {.back = NULL, .front = NULL, .size = 0};
    }
    
    
    void queue_push(struct Queue* input_queue, struct Coordinate input_data) {
    
    
       if (input_queue->size == 0) {
          input_queue->front = (struct queue_node*) malloc(sizeof(struct queue_node));
          input_queue->back = input_queue->front;
       }
       else {
          input_queue->back->next_node = (struct queue_node*) malloc(sizeof(struct queue_node));
          input_queue->back = input_queue->back->next_node;
       }
       check_malloc_fail(input_queue->back);
    
    
       ++input_queue->size;
    
    
       input_queue->back->data = input_data;
       input_queue->back->next_node = NULL;
    }
    
    
    struct Coordinate queue_pop(struct Queue* input_queue) {
    
    
       if (input_queue->size == 0) {
          fprintf(stderr, "attempt to pop empty queue\n");
          return (struct Coordinate){-1,-1};
       }
    
    
       struct queue_node* popped_element = input_queue->front;
       input_queue->front = input_queue->front->next_node;
    
    
       struct Coordinate output = popped_element->data;
       free(popped_element);
       --input_queue->size;
    
    
       return output;
    }

  2. #2
    Registered User
    Join Date
    Feb 2019
    Posts
    824
    I would prefer to allocate the nodes outside the push/pop functions. And to do a more "generic" queue, like this:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    // Generic node structure.
    // Use "polimorphism" to create your own nodes, like:
    //
    //    struct mynode {
    //      NODE node_;    // MUST be the first member!
    //
    //      int n;         // MY node data.
    //    };
    //
    typedef struct node
    {
      struct node *next, *prev;
    } NODE;
    
    typedef struct queue
    {
      struct node *head, *tail;
    } QUEUE;
    
    // Returns NULL in case of error.
    QUEUE *create_queue ( void )
    {
      return calloc ( 1, sizeof ( QUEUE ) );
    }
    
    void queue_push ( QUEUE *q, void *n )
    {
      NODE *nptr = n;
    
      if ( q->tail )
      {
        q->tail->next = nptr;
        nptr->prev = q->tail;
      }
      else
      {
        q->head = nptr;
        nptr->prev = NULL;
      }
    
      q->tail = nptr;
      nptr->next = NULL;
    }
    
    void *queue_pop ( QUEUE *q )
    {
      NODE *n, *p;
    
      n = NULL;
    
      if ( q->tail )
      {
        n = q->tail;
        p = q->tail->prev;
        q->tail = p;
      }
    
      if ( ! q->tail )
        q->head = NULL;
      else
        q->tail->next = NULL;
    
      return n;
    }
    
    void destroy_queue ( QUEUE *q, void ( *dtor ) ( void * ) )
    {
      NODE *n;
    
      while ( q->head )
      {
        n = q->head->next;
    
        if ( dtor )
          dtor ( q->head );
    
        q->head = n;
      }
    
      free ( q );
    }
    
    // ----------------------------
    // Usage example:
    // ----------------------------
    
    // My own node: Notice the first member.
    struct mynode
    {
      NODE node_;
      int n;
    };
    
    // helper function to allocate new nodes.
    static struct mynode *create_node ( int n )
    {
      struct mynode *p;
    
      if ( ! ( p = malloc ( sizeof * p ) ) )
      {
        fprintf ( stderr, "ERROR allocating node (n=%d).\n", n );
    
        // Didn't bother with housekeeping...
        exit ( EXIT_FAILURE );
      }
    
      p->n = n;
    
      return p;
    }
    
    int main ( void )
    {
      QUEUE *q;
      struct mynode *p;
    
      if ( ! ( q = create_queue() ) )
      {
        fputs ( "ERROR creating queue.\n", stderr );
        return EXIT_FAILURE;
      }
    
      p = create_node ( 1 );
      queue_push ( q, p );
    
      p = create_node ( 2 );
      queue_push ( q, p );
    
      p = create_node ( 3 );
      queue_push ( q, p );
    
      // While there is nodes to "pop", show their data
      // and free them.
      while ( p = queue_pop ( q ) )
      {
        printf ( "POP: %d\n", p->n );
        free ( p );
      }
    
      // Destroy the list and all remaining nodes, if any.
      // there will be none, after the loop above.
      // Notice my "destructor" is the free() function.
      destroy_queue ( q, free );
    
      return EXIT_SUCCESS;
    }

  3. #3
    Registered User
    Join Date
    Sep 2018
    Posts
    208
    Thanks a lot for replying flp1969!
    Wow. It's really amazing. I never knew you could do stuff like that (the polymorphism). That's a really neat hack, thanks a lot.

    Took me some time to understand,

    I have some questions

    (1) Do we normally typedef all our structs in C? Why is only queue and node typedef'd and not mynode, in the program?
    Is there a commonly used convention for when to typedef? Is there any reason one should not typedef?

    (2) Would it have been better if we checked whether create_queue() failed, within create_queue()? Is there a reason why we checked for failure in the main function?
    Last edited by Nwb; 10-10-2020 at 11:00 AM.

  4. #4
    Registered User
    Join Date
    May 2012
    Posts
    490
    Quote Originally Posted by Nwb View Post
    Thanks a lot for replying flp1969!
    Wow. It's really amazing. I never knew you could do stuff like that (the polymorphism). That's a really neat hack, thanks a lot.

    Took me some time to understand,

    I have some questions

    (1) Do we normally typedef all our structs in C? Why is only queue and node typedef'd and not mynode, in the program?
    Is there a commonly used convention for when to typedef? Is there any reason one should not typedef?
    That's what we call a "religious question". Most people typedef C structs as a matter of course, a few refuse to do so. If you don't typedef, you don't pollute the global namespace, and also it is apparent that the type is a struct.

    (2) Would it have been better if we checked whether create_queue() failed, within create_queue()? Is there a reason why we checked for failure in the main function?
    Memory allocation can always fail. But in most cases, there's nothing low level code can do about it. It can't send a message to stderr because that might not make sense in the context of the program. It can't terminate because caller might not want a brutal termination. So the best thing to do is to pass the error condition up. If you return a pointer, the natural thing to do is to return a null pointer to indicate failure.
    main() is the highest level function. In this simple test program, it's the level at which we should handle errors.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  5. #5
    Registered User
    Join Date
    Sep 2018
    Posts
    208
    Thanks Malcolm.

    " It can't send a message to stderr because that might not make sense in the context of the program."
    I didn't understand this sentence.

  6. #6
    Registered User
    Join Date
    Feb 2019
    Posts
    824
    Quote Originally Posted by Nwb View Post
    (1) Do we normally typedef all our structs in C? Why is only queue and node typedef'd and not mynode, in the program? Is there a commonly used convention for when to typedef? Is there any reason one should not typedef?
    I don't, but in this case I did hope it looks like an "opaque" type, like FILE...

    (2) Would it have been better if we checked whether create_queue() failed, within create_queue()? Is there a reason why we checked for failure in the main function?
    If create_queue() fails, it'll return NULL. I prefer to check for error from the calling function. This way I would not propagate a lot of error checking around complex code... Notice functions like strcpy() don't check for errors for this same reason.

    []s
    Fred

  7. #7
    Registered User
    Join Date
    May 2012
    Posts
    490
    Quote Originally Posted by Nwb View Post
    Thanks Malcolm.

    " It can't send a message to stderr because that might not make sense in the context of the program."
    I didn't understand this sentence.
    Say it's a Windows program. You can't easily show a message passed to stderr to the user. So no library code that might be called from a Windows environment should rely on stderr being visible.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  8. #8
    Registered User
    Join Date
    Sep 2018
    Posts
    208
    Ok, thanks Fred and Malcolm.

  9. #9
    Registered User
    Join Date
    Sep 2018
    Posts
    208
    One more question.

    Code:
    void destroy_queue ( QUEUE *q, void ( *dtor ) ( void * ) )
    {
      NODE *n;
     
      while ( q->head )
      {
        n = q->head->next;
     
        if ( dtor )
          dtor ( q->head );
     
        q->head = n;
      }
     
      free ( q );
    }

    Can we put the declaration of NODE *n inside the while loop?
    Like so:

    Code:
    void destroy_queue ( QUEUE *q, void ( *dtor ) ( void * ) )
    {
      while ( q->head )
      {
        NODE *n = q->head->next;
    
        if ( dtor )
          dtor ( q->head );
    
        q->head = n;
      }
    
      free ( q );
    }


    Which way is preferred?

  10. #10
    Registered User
    Join Date
    Feb 2019
    Posts
    824
    Quote Originally Posted by Nwb View Post
    Can we put the declaration of NODE *n inside the while loop?

    In this case, yes, you can.
    [
    Quote Originally Posted by Nwb
    Which way is preferred?
    I prefer to declare all my local objects in the beggining of the function, in rare cases I use a block declaration (when I want to reuse the identifier in different contexts). But it's just my way of doing things, not a strict rule.

  11. #11
    Registered User
    Join Date
    Sep 2020
    Posts
    62
    Could I have represented the Queue in a different way? I intially thought about using an array, but I realized that it is not possible to shave off a specific amount of bytes from the front.
    When you use an array you actually don't remove numbers from the array, you only change markers for front and rear.
    This tutorial explains it nicely.
    4.2 Implementation of queue using Arrays | data structures - YouTube

  12. #12
    Registered User
    Join Date
    Sep 2018
    Posts
    208
    ok, thanks for replying Fred.

    @thmm thanks for replying, yeah, looks like linked nodes are the way to go.

  13. #13
    Registered User
    Join Date
    Feb 2019
    Posts
    824
    Quote Originally Posted by Nwb View Post
    ok, thanks for replying Fred.
    @thmm thanks for replying, yeah, looks like linked nodes are the way to go.
    Not THE way to go... You could use dynamic arrays:
    Code:
    int *queue = NULL;
    size_t elements = 0;
    
    int push( int x )
    {
      int *p;
    
      p = realloc( queue, sizeof x * ++elements );
      if ( p )
      {
        p[ elements - 1 ] = x;
        queue = p;
      }
    
      return !!p;
    }
    
    long long pop( void )
    {
      int x;
    
      if ( elements )
      {
        x = queue[ --elements ];
        queue = realloc( queue, elements );  // shrinking a buffer will not cause errors!
        return x;
      }
    
      return LLONG_MIN;  // error condition.
    }
    Something like this.

  14. #14
    Registered User
    Join Date
    Feb 2019
    Posts
    824
    Sorry... I realize now my examples are stacks, not queues... When 'poping' get the first element and copy the rest of them to the beggining, changing the size of the buffer to less one element.
    Change the linked list version accordinly, as well...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Queue implementation!
    By proudT in forum C Programming
    Replies: 3
    Last Post: 10-24-2015, 11:06 AM
  2. Question regarding queue implementation
    By jjwooyoung in forum C++ Programming
    Replies: 1
    Last Post: 07-27-2015, 12:22 AM
  3. Queue implementation in C
    By cerr in forum C Programming
    Replies: 13
    Last Post: 01-11-2010, 12:30 PM
  4. Queue implementation
    By kolliash in forum C Programming
    Replies: 1
    Last Post: 06-01-2008, 08:25 AM
  5. Queue implementation
    By Hunter2 in forum C++ Programming
    Replies: 3
    Last Post: 02-19-2005, 01:50 PM

Tags for this Thread