Thread: 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;
}

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;
}

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.

Originally Posted by Nwb

(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

Ok, thanks Fred and Malcolm.

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?

Originally Posted by Nwb

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

In this case, yes, you can.
[

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.

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

ok, thanks for replying Fred.

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

Originally Posted by Nwb

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.

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...