Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Queue - can not delete last element

13 views
Skip to first unread message

arnuld

unread,
Jun 13, 2011, 3:30:36 AM6/13/11
to
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


----------------------------
num = 10
num = 0
[arnuld@dune C]$


--
www.lispmachine.wordpress.com
find my email-ID @above blog

Dr Nick

unread,
Jun 13, 2011, 3:38:36 AM6/13/11
to
arnuld <sun...@invalid.address> writes:

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

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

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.

arnuld

unread,
Jun 13, 2011, 4:18:22 AM6/13/11
to
> On Mon, 13 Jun 2011 08:38:36 +0100, Dr Nick wrote:


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

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 */
{
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;
}
}
}

Ike Naar

unread,
Jun 13, 2011, 5:25:24 AM6/13/11
to
On 2011-06-13, arnuld <sun...@invalid.address> wrote:
> 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 */
> {
> free(d);
> s->head = s->tail = NULL;
> }
> else if((NULL == d->next) && d->prev) /* removing tail */
> {
> s->tail = d->prev;
> d->prev->next = NULL;

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

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

arnuld

unread,
Jun 13, 2011, 7:31:12 AM6/13/11
to
> On Mon, 13 Jun 2011 09:25:24 +0000, Ike Naar wrote:


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

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;

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

Ike Naar

unread,
Jun 13, 2011, 8:36:56 AM6/13/11
to
On 2011-06-13, arnuld <sun...@invalid.address> wrote:
>> On Mon, 13 Jun 2011 09:25:24 +0000, Ike Naar wrote:
>> 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;
>
> That sets s->head. What about the d->next->prev, It will still point to
> d and then to garbage after free(d).

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

arnuld

unread,
Jun 13, 2011, 9:29:29 AM6/13/11
to
> On Mon, 13 Jun 2011 12:36:56 +0000, Ike Naar wrote:

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

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

ouch! yes, you did.

I wonder why simplicity is so difficult to understand :-/

0 new messages