1

I've been working on an assignment involving implementing queues that hold void pointers so that they can be generalized for any type of data. I'm currently encountering an odd problem though where dequeuing nodes reduces the size of the list but does not return the nodes I expect it to. Omitting a call to free() in the dequeue operation corrects for this, but as I want to free dequeued nodes this is not desirable. Any tips?

Test run: routine.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "queue.h"

int main() {
  queue test = make_queue();
  enqueue("One", test);
  enqueue("Two", test);
  printf("Item is %s!\n", (char *)dequeue(test));
  printf("Item is %s!\n", (char *)dequeue(test));
  return 0;
}

queue.h

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
/* A queue is implemented as a pointer to a structure not specified here. */

typedef struct queue_structure *queue;

struct node {
  struct node * next;
  void * data;
};

struct queue_structure {
  struct node * head;
  struct node * tail;
};

/* List of function protocols. */
bool is_empty_queue(queue q);

/* The make_queue function returns a newly created queue with no values
   stored in it.
*/

queue make_queue() {
  queue newQueue = malloc(sizeof(struct queue_structure));
  return newQueue;
}

/* The enqueue function adds a value to a queue.  Although this function
   does not change the pointer q, fields of the structure to which q
   points may be modified in the course of a call to this function.
*/

void enqueue(void *value, queue q) {
  struct node * newNode = (struct node *)malloc(sizeof(struct node));
  newNode->data = value;    
  if(is_empty_queue(q))
    q->tail = newNode;
  newNode->next = q->head;
  q->head = newNode;
}

/* The dequeue function removes a value from a queue and returns it.
   Although this function does not change the pointer q, fields of the
   structure to which q points may be modified in the course of a call to
   this function.

   It is a precondition of this function that at least one value is stored
   in the queue.
*/

void *dequeue(queue q) {
  if(!q->head->next) { // Only a single item in the queue.
    printf("Only one item in queue!\n");
    struct node * to_dequeue = q->tail;
    void * data = q->head->data;
    free(to_dequeue);
    q->head = NULL;
    q->tail = NULL;
    return data;
  }
  else { // Multiple items in the queue.
    printf("Several items in queue!\n");
    struct node * to_dequeue = q->tail;
    void * data = q->tail->data;
    struct node * trace = q->head;
    while(trace->next && trace->next != q->tail)
      trace = trace->next;
    free(to_dequeue);
    q->tail = trace;
    q->tail->next = NULL;
    return data;
  }
}

/* The front_of_queue function returns the value at the front of a queue
   (that is, the one least recently added to the queue) without removing
   that value from the queue.  It has no side effect.

   It is a precondition of this function that at least one value is stored
   in the queue.
*/

void *front_of_queue(queue q) {
  return q->head->data;
}

/* The is_empty_queue function determines whether a queue is empty,
   returning the true Boolean value if no values are stored in the queue
   and the false Boolean value if one or more values are stored in the
   queue.
*/

bool is_empty_queue(queue q) {
  if(q->head)
    return 1;
  return 0;
}
Improve this question
2
  • A small note: You are mixing interface and implementation by having everything in a single header file. This means you can't have two different source files use the queue, because you will get linker errors. Put the implementation (the actual code in the functions) in a separate source file, and only have the structures and function prototypes in the header file. Commented Jan 27, 2012 at 6:17
  • Another note: You are expecting that the arguments to the functions are valid, which they might not be. Also, in for example dequeue, you will have to check for an empty queue. It might be ok for a simple homework application, but good habits (like checking arguments and similar) are good to learn early. :) Commented Jan 27, 2012 at 6:20

1 Answer 1

Reset to default
1

You don't initialise head and tail to NULL in make_queue and you have got your emptiness test wrong,

bool is_empty_queue(queue q) {
  if(q->head)
    return 1;
  return 0;
}

which makes enqueue behave oddly.

void enqueue(void *value, queue q) {
  struct node * newNode = (struct node *)malloc(sizeof(struct node));
  newNode->data = value;    
  if(is_empty_queue(q))
    q->tail = newNode;
  newNode->next = q->head;
  q->head = newNode;
}

Case 1, perchance head and tail are NULL initially

head -> 0; tail -> 0  // now enqueue 1
is_empty_queue(q) returns 0 since q->head == NULL, so q->tail still points to 0
n(1)->next = 0
head = n(1)

results in
head -> n(1) -> 0; tail -> 0  // next enqueue 2
is_empty_queue(q) returns 1 since q->head = n(1) != 0, so
q->tail = n(2)
n(2)->next = n(1)
q->head = n(2)

result:
head -> n(2) -> n(1) -> 0; tail -> n(2)

and all further enqueue operations will leave head == tail. But if you now dequeue:

struct node * to_dequeue = q->tail;   // n(2)
void * data = q->tail->data;
struct node * trace = q->head;        // n(2)
while(trace->next && trace->next != q->tail)  // n(2) -> n(1) -> 0
  trace = trace->next;                // trace = n(1)
free(to_dequeue);                     // free n(2)
q->tail = trace;                      // tail -> n(1)
q->tail->next = NULL;                 // already had that

and head is a dangling pointer.

Case 2, perchance head isn't NULL initially.

head -> x; tail -> y // enqueue 1
is_empty_queue(q) returns 1 because q->head == x != 0
q->tail = n(1)
n(1)->next = x
q->head = n(1)

head -> n(1) -> x; tail -> n(1) // now enqueue 2
is_empty_queue(q) returns 1 because q->head == n(1)
q->tail = n(2)
n(2)->next = n(1)
q->head = n(2)

head -> n(2) -> n(1) -> x; tail -> n(2)

The only difference is that now n(1)->next != 0, then if you dequeue, trace will be set to the wild 'pointer' x and then x->next is checked, but since x was an indeterminate bit pattern, that will often cause a segfault.

Unless I overlooked something, initialising head and tail on construction, fixing is_empty_queue and checking for emptiness on dequeue will give you a working programme.

But if the queue is long, the dequeue operation is slow since it has to traverse the entire queue to find the penultimate element to update tail. You can have both, enqueue and dequeue, O(1) operations if you enqueue at the tail position and dequeue from head.

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

1 Comment

I think : (emptQueue) if(element.first == NULL){ return TRUE; else ... is best and fast :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.