Queue - can not delete last element

A

arnuld

WANTED: to delete element from FIFO (Queue)
WHAT I GOT: element is still there with value zero (it garbage value I
guess)

Dequeue deletes last element from this Queue, from the tail. I can't make
out whats wrong here:




/* A Queue (FIFO) implementation using doubly-linked list. All
operations are based on page 70, section 2.4 "Data Structures and
* Algorithms by Aho, Hopcraft and Ullman".
*
* VERSION 0.0
*
*/

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

enum { VAL_SUCC = 0, VAL_ERR = 1};

struct dlqueue
{
int num;
struct dlqueue* next;
struct dlqueue* prev;
};


struct dlqlist
{
struct dlqueue* head;
struct dlqueue* tail;
};



int enqueue(struct dlqlist*, int);
int dequeue(struct dlqlist*);
struct dlqueue* front(struct dlqlist*);
void makenull(struct dlqlist*);
int empty(struct dlqlist*);
void print_queue(struct dlqlist* );

int main(void)
{
struct dlqlist* s = malloc(1 * sizeof *s);
if(NULL == s)
{
fprintf(stderr,"IN: %s @%d: Out of Memory\n", __FILE__, __LINE__);
return EXIT_FAILURE;
}
else
{
s->head = s->tail = NULL;
}

enqueue(s, 10);
enqueue(s, 11);
print_queue(s);

dequeue(s);
printf("\n\n----------------------------\n");
print_queue(s);

return EXIT_SUCCESS;
}



int enqueue(struct dlqlist* s, int i)
{
int ret;
if(NULL == s)
{
fprintf(stderr, "IN: %s @ %d: Invalid Args\n", __FILE__, __LINE__);
ret = VAL_ERR;
}
else if(NULL == s->head && NULL == s->tail)
{
struct dlqueue* p = malloc(1 * sizeof *p);
if(NULL == p)
{
fprintf(stderr,"IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
ret = VAL_ERR;
}
else
{
p->num = i;
p->prev = p->next = NULL;

s->head = s->tail = p;
ret = VAL_SUCC;
}
}
else if(NULL == s->head || NULL == s->tail)
{
fprintf(stderr, "IN: %s @%d: Serious error.", __FILE__, __LINE__);
fprintf(stderr,"List one of the list's head/tail is null while
other is not\n");
ret = VAL_ERR;
}
else
{
struct dlqueue* p = malloc(1 * sizeof *p);
if(NULL == p)
{
fprintf(stderr,"IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
ret = VAL_ERR;
}
else
{
p->num = i;
p->prev = p->next = NULL;

s->tail->next = p;
p->prev = s->tail;
s->tail = p;
ret = VAL_SUCC;
}
}

return ret;
}



int dequeue(struct dlqlist* s)
{
int ret;
if(NULL == s)
{
fprintf(stderr, "IN: %s @ %d: Invalid Args\n", __FILE__, __LINE__);
ret = VAL_ERR;
}
else if(NULL == s->head && NULL == s->tail)
{
printf("Bothing to Dequeue in empty Queue\n");
ret = VAL_SUCC;
}
else if(NULL == s->head || NULL == s->tail)
{
fprintf(stderr, "IN: %s @%d: Serious error.", __FILE__, __LINE__);
fprintf(stderr,"List one of the list's head/tail is null while
other is not\n");
ret = VAL_ERR;
}
else
{
struct dlqueue* p = s->tail;
if(NULL == s->tail->next && NULL == s->head->next) /* if last
element */
{
s->head = s->tail = NULL;
}
else
{
s->tail = s->tail->prev;
}

free(p);
ret = VAL_SUCC;
}

return ret;
}




void print_queue(struct dlqlist* s)
{
if(NULL == s)
{
fprintf(stderr, "IN: %s @ %d: Invalid Args\n", __FILE__, __LINE__);
}
else if(NULL == s->head && NULL == s->tail)
{
printf("Nothing to print\n");
}
else if(NULL == s->head || NULL == s->tail)
{
fprintf(stderr, "IN: %s @%d: Serious error.", __FILE__, __LINE__);
fprintf(stderr,"List one of the list's head/tail is null while
other is not\n");
}
else
{
struct dlqueue* p = s->head;
while(p)
{
printf("num = %d\n", p->num);
p = p->next;
}
}
}

======================= OUTPUT ========================
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra fifo-dl.c
[arnuld@dune C]$ ./a.out
num = 10
num = 11
 
D

Dr Nick

arnuld said:
WANTED: to delete element from FIFO (Queue)
WHAT I GOT: element is still there with value zero (it garbage value I
guess)

Dequeue deletes last element from this Queue, from the tail. I can't make
out whats wrong here:
Click to expand...
int dequeue(struct dlqlist* s)
{
int ret;
if(NULL == s)
{
fprintf(stderr, "IN: %s @ %d: Invalid Args\n", __FILE__, __LINE__);
ret = VAL_ERR;
}
else if(NULL == s->head && NULL == s->tail)
{
printf("Bothing to Dequeue in empty Queue\n");
ret = VAL_SUCC;
}
else if(NULL == s->head || NULL == s->tail)
{
fprintf(stderr, "IN: %s @%d: Serious error.", __FILE__, __LINE__);
fprintf(stderr,"List one of the list's head/tail is null while
other is not\n");
ret = VAL_ERR;
}
else
{
struct dlqueue* p = s->tail;
if(NULL == s->tail->next && NULL == s->head->next) /* if last
element */
{
s->head = s->tail = NULL;
}
else
{
s->tail = s->tail->prev;
}

free(p);
ret = VAL_SUCC;
}

return ret;
}
Click to expand...

Although you update the tail pointer, you don't change the "next"
pointer of the node immediately before the node you are deleting. So
when you come to print, you carry on into the deleted item.

You need p->prev->next = NULL or similar before you free p.
 
A

arnuld

Although you update the tail pointer, you don't change the "next"
pointer of the node immediately before the node you are deleting. So
when you come to print, you carry on into the deleted item.
Click to expand...
You need p->prev->next = NULL or similar before you free p.
Click to expand...

Excellent. Although I found the problem before you posted but you gave me
a new idea on how to use pointer variables. I have created a function
which will remove element from anywhere in Queue and that it ran in first
compilation :) . Check it out, dequeue_aywhere() :




/* A Queue (FIFO) implementation using doubly-linked list. All
operations are based on page 70, section 2.4 "Data Structures and
* Algorithms by Aho, Hopcraft and Ullman".
*
* VERSION 0.0
*
*/

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

enum { VAL_SUCC = 0, VAL_ERR = 1};

struct dlqueue
{
int num;
struct dlqueue* next;
struct dlqueue* prev;
};


struct dlqlist
{
struct dlqueue* head;
struct dlqueue* tail;
};



int enqueue(struct dlqlist*, int);
int dequeue(struct dlqlist*);
struct dlqueue* front(struct dlqlist*);
void makenull(struct dlqlist*);
int empty(struct dlqlist*);
void print_queue(struct dlqlist* );


int dequeue_anywhere(struct dlqlist*s , int numd);
void remove_element(struct dlqlist* s, struct dlqueue* d);


int main(void)
{
struct dlqlist* s = malloc(1 * sizeof *s);
if(NULL == s)
{
fprintf(stderr,"IN: %s @%d: Out of Memory\n", __FILE__, __LINE__);
return EXIT_FAILURE;
}
else
{
s->head = s->tail = NULL;
}

enqueue(s, 10);
enqueue(s, 11);
enqueue(s, 12);
enqueue(s, 13);
print_queue(s);

dequeue_anywhere(s,12);
printf("\n\n----------------------------\n");
print_queue(s);

/*
dequeue(s);
printf("\n\n----------------------------\n");
print_queue(s);

dequeue(s);
printf("\n\n----------------------------\n");
print_queue(s);


dequeue(s);
printf("\n\n----------------------------\n");
print_queue(s);
*/
return EXIT_SUCCESS;
}



/* Adds an element to tail of Queue */
int enqueue(struct dlqlist* s, int i)
{
int ret;
if(NULL == s)
{
fprintf(stderr, "IN: %s @ %d: Invalid Args\n", __FILE__, __LINE__);
ret = VAL_ERR;
}
else if(NULL == s->head && NULL == s->tail)
{
struct dlqueue* p = malloc(1 * sizeof *p);
if(NULL == p)
{
fprintf(stderr,"IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
ret = VAL_ERR;
}
else
{
p->num = i;
p->prev = p->next = NULL;

s->head = s->tail = p;
ret = VAL_SUCC;
}
}
else if(NULL == s->head || NULL == s->tail)
{
fprintf(stderr, "IN: %s @%d: Serious error.", __FILE__, __LINE__);
fprintf(stderr,"List one of the list's head/tail is null while
other is not\n");
ret = VAL_ERR;
}
else
{
struct dlqueue* p = malloc(1 * sizeof *p);
if(NULL == p)
{
fprintf(stderr,"IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
ret = VAL_ERR;
}
else
{
p->num = i;
p->prev = p->next = NULL;

s->tail->next = p;
p->prev = s->tail;
s->tail = p;
ret = VAL_SUCC;
}
}

return ret;
}



int dequeue(struct dlqlist* s)
{
int ret;
if(NULL == s)
{
fprintf(stderr, "IN: %s @ %d: Invalid Args\n", __FILE__, __LINE__);
ret = VAL_ERR;
}
else if(NULL == s->head && NULL == s->tail)
{
printf("Nothing to Dequeue()\n");
ret = VAL_SUCC;
}
else if(NULL == s->head || NULL == s->tail)
{
fprintf(stderr, "IN: %s @%d: Serious error.", __FILE__, __LINE__);
fprintf(stderr,"List one of the list's head/tail is null while
other is not\n");
ret = VAL_ERR;
}
else
{
/* try removing from tail and right there we will get Segfault */
struct dlqueue* p = s->head;
if(NULL == s->head->next && NULL == s->tail->next) /* if last
element */
{
s->head = s->tail = NULL;
}
else
{
s->head = s->head->next;
}

free(p);
ret = VAL_SUCC;
}

return ret;
}


int dequeue_anywhere(struct dlqlist*s , int numd)
{
int ret;
if(NULL == s)
{
fprintf(stderr, "IN: %s @ %d: Invalid Args\n", __FILE__, __LINE__);
ret = VAL_ERR;
}
else if(NULL == s->head && NULL == s->tail)
{
printf("Nothing to Dequeue()\n");
ret = VAL_SUCC;
}
else if(NULL == s->head || NULL == s->tail)
{
fprintf(stderr, "IN: %s @%d: Serious error.", __FILE__, __LINE__);
fprintf(stderr,"List one of the list's head/tail is null while
other is not\n");
ret = VAL_ERR;
}
else
{
struct dlqueue* p = s->head;
for(; p; p = p->next)
{
if(numd == p->num)
{
remove_element(s,p);
}
}
ret = VAL_SUCC;
}

return ret;
}


void remove_element(struct dlqlist* s, struct dlqueue* d)
{
if(NULL == d->next && (NULL == s->head->next && NULL == s->tail-
next)) /* only one element in queue */
Click to expand...
{
free(d);
s->head = s->tail = NULL;
}
else if((NULL == d->next) && d->prev) /* removing tail */
{
s->tail = d->prev;
d->prev->next = NULL;
}
else if(d->next && (NULL == d->prev)) /* removing head */
{
s->head = d->next;
s->head->prev = NULL;
free(d);
}
else /* removing from center or somewhere */
{
d->prev->next = d->next;
d->next->prev = d->prev;
free(d);
}
}


void print_queue(struct dlqlist* s)
{
if(NULL == s)
{
fprintf(stderr, "IN: %s @ %d: Invalid Args\n", __FILE__, __LINE__);
}
else if(NULL == s->head && NULL == s->tail)
{
printf("Nothing to print\n");
}
else if(NULL == s->head || NULL == s->tail)
{
fprintf(stderr, "IN: %s @%d: Serious error.", __FILE__, __LINE__);
fprintf(stderr,"List one of the list's head/tail is null while
other is not\n");
}
else
{
struct dlqueue* p = s->head;
while(p)
{
printf("num = %d\n", p->num);
p = p->next;
}
}
}
 
I

Ike Naar

void remove_element(struct dlqlist* s, struct dlqueue* d)
{
if(NULL == d->next && (NULL == s->head->next && NULL == s->tail-
{
free(d);
s->head = s->tail = NULL;
}
else if((NULL == d->next) && d->prev) /* removing tail */
{
s->tail = d->prev;
d->prev->next = NULL;
Click to expand...

You don't free d here?
}
else if(d->next && (NULL == d->prev)) /* removing head */
{
s->head = d->next;
s->head->prev = NULL;
free(d);
}
else /* removing from center or somewhere */
{
d->prev->next = d->next;
d->next->prev = d->prev;
free(d);
}
}
Click to expand...

You could simplify it a bit, like this:

void remove_element(struct dlqlist* s, struct dlqueue* d)
{
if (d->next == NULL)
s->tail = d->prev;
else
d->next->prev = d->prev;
if (d->prev == NULL)
s->head = d->next;
else
d->prev->next = d->next;
free(d);
}
 
A

arnuld

You could simplify it a bit, like this:

void remove_element(struct dlqlist* s, struct dlqueue* d) {
if (d->next == NULL)
s->tail = d->prev;
else
d->next->prev = d->prev;
if (d->prev == NULL)
s->head = d->next;
Click to expand...

That sets s->head. What about the d->next->prev, It will still point to
d and then to garbage after free(d).
else
d->prev->next = d->next;
Click to expand...

Same here, what about: d->next->prev which still points to d ?
 
I

Ike Naar

That sets s->head. What about the d->next->prev, It will still point to
d and then to garbage after free(d).
Click to expand...

d->next->prev was set to d->prev two lines earlier.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Remving an element from Queue 37
Queue in C 25
Queue in C 0
dequeue() not working 9
Array implementation of Stack 80
wcstombs() problem 16
A Queue implementation of doubly linked list in C 44
Stack using doubly linked list 1

Members online

Total: 34 (members: 4, guests: 30)
Robots: 315

Forum statistics

Threads
473,755
Messages
2,569,535
Members
45,007
Latest member
obedient dusk

Latest Threads

Top