c - Queue/dequeue oddity? -

c - Queue/dequeue oddity? -

i've been working on assignment involving implementing queues hold void pointers can generalized type of data. i'm encountering odd problem though dequeuing nodes reduces size of list not homecoming nodes expect to. omitting phone call free() in dequeue operation corrects this, want free dequeued nodes not desirable. 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 %s!\n", (char *)dequeue(test)); printf("item %s!\n", (char *)dequeue(test)); homecoming 0; }

queue.h

#include <stdbool.h> #include <stdlib.h> #include <stdio.h> /* queue implemented pointer construction 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); /* make_queue function returns newly created queue no values stored in it. */ queue make_queue() { queue newqueue = malloc(sizeof(struct queue_structure)); homecoming newqueue; } /* enqueue function adds value queue. although function not alter pointer q, fields of construction q points may modified in course of study of phone call 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; } /* dequeue function removes value queue , returns it. although function not alter pointer q, fields of construction q points may modified in course of study of phone call function. precondition of function @ to the lowest degree 1 value stored in queue. */ void *dequeue(queue q) { if(!q->head->next) { // single item in queue. printf("only 1 item in queue!\n"); struct node * to_dequeue = q->tail; void * info = q->head->data; free(to_dequeue); q->head = null; q->tail = null; homecoming data; } else { // multiple items in queue. printf("several items in queue!\n"); struct node * to_dequeue = q->tail; void * info = 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; homecoming data; } } /* front_of_queue function returns value @ front end of queue (that is, 1 to the lowest degree added queue) without removing value queue. has no side effect. precondition of function @ to the lowest degree 1 value stored in queue. */ void *front_of_queue(queue q) { homecoming q->head->data; } /* is_empty_queue function determines whether queue empty, returning true boolean value if no values stored in queue , false boolean value if 1 or more values stored in queue. */ bool is_empty_queue(queue q) { if(q->head) homecoming 1; homecoming 0; }

you don't initialise head , tail null in make_queue , have got emptiness test wrong,

bool is_empty_queue(queue q) { if(q->head) homecoming 1; homecoming 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 , tail null initially

head -> 0; tail -> 0 // enqueue 1 is_empty_queue(q) returns 0 since q->head == null, q->tail still points 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, q->tail = n(2) n(2)->next = n(1) q->head = n(2) result: head -> n(2) -> n(1) -> 0; tail -> n(2)

and farther enqueue operations leave head == tail. if dequeue:

struct node * to_dequeue = q->tail; // n(2) void * info = 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; // had

and head 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) // 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 difference n(1)->next != 0, if dequeue, trace set wild 'pointer' x , x->next checked, since x indeterminate bit pattern, cause segfault.

unless overlooked something, initialising head , tail on construction, fixing is_empty_queue , checking emptiness on dequeue give working programme.

but if queue long, dequeue operation slow since has traverse entire queue find penultimate element update tail. can have both, enqueue , dequeue, o(1) operations if enqueue @ tail position , dequeue head.

c queue free