dequeue() not working

[arnuld]

WANTED: to dequeue an element from Queue.
GOT: nothing happening

/* A queue implementation with the operations that I need:
* (1) Add an element to the front (head) of the queue
* (2) Remove an element from rear (tail) of the queue
* (2) remove an element with a unique ID (string constant)
* (3) compare 2 elements (string comparison)
* (4) print queue
*
* VERSION 0.0
*/

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

enum { SIZE_ID = 100, SIZE_ARR = 20, REPS = 3 };

struct myQ
{
char id[SIZE_ID+1];
struct myQ* next;
};

struct myList
{
struct myQ* head;
struct myQ* tail;
};



struct myList* allocmyList(void);
int enqueue(struct myList* s, const char* id);
struct myQ* dequeue(struct myList** s);
void removeElement(struct myList* s, const char* id);
struct myQ* searchElement(struct myList* s, const char* is, struct myQ**
pr);
void deleteElement(struct myList* s, struct myQ* q, struct myQ* prev);
void printQ(struct myList* s);
/*void reverseQueue(struct myList** s); */


int main(void)
{
struct myList* s = allocmyList();
int i;
for(i = 0; i < REPS; ++i)
{
int r;
char arrc[SIZE_ARR+1];
r = sprintf(arrc, "%d", i);
if(0 > r)
{
printf("ERROR-SPRINF() = %d\n", r);
}
else
{
enqueue(s, arrc);
}
printf("s->head = %p, s->tail = %p\n", (void*)s->head, (void*)s-

tail);

}

printQ(s);
/*
for(i = 0; i < REPS; ++i)
{
int r;
char arrc[SIZE_ARR+1];
r = sprintf(arrc, "%d", i);
if(0 > r)
{
printf("ERROR-SPRINF() = %d\n", r);
}
else
{
removeElement(s, arrc);
}
}
*/
dequeue(&s);
printQ(s);
free(s);

return 0;
}


int enqueue(struct myList* s, const char* id)
{
struct myQ *p;
if(NULL == s || NULL == id) return -1;
p = malloc(1 * (sizeof *p));
if(NULL == p) return -1;
strcpy(p->id, id);

if(s->head)
{
p->next = s->head;
s->head = p;
}
else
{
s->head = s->tail = p;
}

return 1;
}


struct myQ* dequeue(struct myList** s)
{
struct myQ *temp, *prev;
if(NULL == s || NULL == *s) return 0;
if(NULL == (*s)->head) return 0;
prev = (*s)->head;
temp = (*s)->head;
if(NULL == (*s)->head->next)
{
struct myQ* retp = (*s)->head;
(*s)->head = (*s)->tail = NULL;
return retp;
}

while(temp->next)
{
prev = temp;
temp = temp->next;
}

(*s)->tail = prev;

return temp;
}


void removeElement(struct myList* s, const char* id)
{
struct myQ *p, *prev;
if(NULL == s || NULL == id) return;
p = searchElement(s, id, &prev);
if(p)
{
deleteElement(s, p, prev);
}
}


struct myQ* searchElement(struct myList* s, const char* id, struct myQ**
pr)
{
struct myQ *prev, *cur;
prev = s->head;
for(cur = s->head; cur; cur = cur->next)
{
if(0 == strcmp(cur->id, id)) { *pr = prev; return cur;}
else prev = cur;
}

return NULL;
}


void deleteElement(struct myList* s, struct myQ* q, struct myQ* prev)
{
if(0 == strcmp(s->head->id, q->id)) /* removing head */
{
s->head = q->next;
free(q);
}
else
{
prev->next = q->next;
free(q);
}
}

void printQ(struct myList* s)
{
if(s)
{
struct myQ* t;
for(t = s->head; t; t = t->next) printf("ID = %s\n", t->id);
}
else
{
printf("Nothing to print\n");
}

printf("--------------------------------\n");
}


struct myList* allocmyList(void)
{
struct myList* p = malloc(1 * (sizeof *p));
if(NULL == p) exit(EXIT_FAILURE);
p->head = NULL;
p->tail = NULL;
return p;
}


/* --------------------------------------
void reverseQueue(struct myList** s)
{
return;
}
*/


========================= OUTPUT =============================
/home/arnuld/programs/C $ gcc -ansi -pedantic -Wall -Wextra queue.c
/home/arnuld/programs/C $ ./a.out
s->head = 0x804a018, s->tail = 0x804a018
s->head = 0x804a088, s->tail = 0x804a018
s->head = 0x804a0f8, s->tail = 0x804a018
ID = 2
ID = 1
ID = 0

 

[Ike Naar]

struct myQ* dequeue(struct myList** s)
{
struct myQ *temp, *prev;
if(NULL == s || NULL == *s) return 0;
if(NULL == (*s)->head) return 0;
prev = (*s)->head;
temp = (*s)->head;
if(NULL == (*s)->head->next)
{
struct myQ* retp = (*s)->head;
(*s)->head = (*s)->tail = NULL;
return retp;
}

while(temp->next)
{
prev = temp;
temp = temp->next;
}

(*s)->tail = prev;

Didn't you forget to set prev->next to NULL here?

return temp;
}

The code above could be simplified in a couple of ways.

First, you can change the type of s to struct mylist*
and replace every (*s) by s.
(and of course, change the call dequeue(&s) to dequeue(s)).

Second, the tail pointer in a struct MyList does not add
much value, so you might as well get rid of it. The last
element in a list is already characterized by element->next
being NULL, and it is that property that you use everywhere.

 

[Ike Naar]

First, you can change the type of s to struct mylist*

Typo, "myList" should be "myList".

Second, the tail pointer in a struct MyList does not add

Typo, "MyList" should be "myList".

 

[Ike Naar]

Typo, "myList" should be "myList".

Okay, you get the point ;-)

 

[Johann Klammer]

WANTED: to dequeue an element from Queue.
GOT: nothing happening

/* A queue implementation with the operations that I need:
* (1) Add an element to the front (head) of the queue
* (2) Remove an element from rear (tail) of the queue

Do it the other way around and add to the end/remove from the start.
It should be quicker and simpler (you have a next pointer to use for head).

 

[Neil Cerutti]

WANTED: to dequeue an element from Queue.
GOT: nothing happening

/* A queue implementation with the operations that I need:
* (1) Add an element to the front (head) of the queue
* (2) Remove an element from rear (tail) of the queue
* (2) remove an element with a unique ID (string constant)
* (3) compare 2 elements (string comparison)
* (4) print queue
*
* VERSION 0.0
*/

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

enum { SIZE_ID = 100, SIZE_ARR = 20, REPS = 3 };

struct myQ
{
char id[SIZE_ID+1];
struct myQ* next;
};

struct myList
{
struct myQ* head;
struct myQ* tail;
};

Implementing linked lists in C may be like walking for most of
the people here, but I think you will benefit by writing down
some notes here.

Along with the struct write down the invariants for the
structures.

For example:

struct myQ
{
char id[SIZE_ID+1]; # null-terminated string.
struct myQ* next; # pointer to the next element or NULL.
};

struct myList
{
struct myQ* head; # pointer to first item in list or NULL
struct myQ* tail; # pointer to last item in list or NULL
};

struct myList* allocmyList(void);
int enqueue(struct myList* s, const char* id);
struct myQ* dequeue(struct myList** s);
void removeElement(struct myList* s, const char* id);
struct myQ* searchElement(struct myList* s, const char* is, struct myQ**
pr);
void deleteElement(struct myList* s, struct myQ* q, struct myQ* prev);
void printQ(struct myList* s);
/*void reverseQueue(struct myList** s); */


int main(void)
{
struct myList* s = allocmyList();
int i;
for(i = 0; i < REPS; ++i)
{
int r;
char arrc[SIZE_ARR+1];
r = sprintf(arrc, "%d", i);
if(0 > r)
{
printf("ERROR-SPRINF() = %d\n", r);
}
else
{
enqueue(s, arrc);
}
printf("s->head = %p, s->tail = %p\n", (void*)s->head, (void*)s-

tail);

}

printQ(s);
/*
for(i = 0; i < REPS; ++i)
{
int r;
char arrc[SIZE_ARR+1];
r = sprintf(arrc, "%d", i);
if(0 > r)
{
printf("ERROR-SPRINF() = %d\n", r);
}
else
{
removeElement(s, arrc);
}
}
*/
dequeue(&s);
printQ(s);
free(s);

return 0;
}


int enqueue(struct myList* s, const char* id)
{
struct myQ *p;
if(NULL == s || NULL == id) return -1;

This type of error checking is the equivalent of crotchless
underpants. Why bother? Anybody careless enough to pass NULL as
either of those arguments will not be checking the return value.

p = malloc(1 * (sizeof *p));
if(NULL == p) return -1;
strcpy(p->id, id);

You must use strncpy with SIZE_ID here to protect against
overflow of p->id.

if(s->head)
{
p->next = s->head;
s->head = p;
}
else
{
s->head = s->tail = p;

Checking invariants, in this branch p->next is left undefined.

}
return 1;
}

I suggest paring down the interface to a minimal singly-linked
list with head and tail pointers, with perhaps an apply function
to allow you to do some tests.

The interface is confusing.

For example, your search function:

struct myQ* searchElement(struct myList* s, const char* id, struct myQ**
pr)

What is pr supposed to be?

dequeue and enqueue are function names without obvious meanings.
push_front and push_back along with pop_front and pop_back would
be easier to comprehend.

 

[Joe keane]

Do it the other way around and add to the end/remove from the start.
It should be quicker and simpler (you have a next pointer to use for head).

question

What do you call three-quarters of a deque?

e.g.

add to front
add to back
remove from front

 

[Martin Shobe]

question

What do you call three-quarters of a deque?

e.g.

add to front
add to back
remove from front

output-restricted deque.

Martin Shobe

 

[Heikki Kallasjoki]

What do you call three-quarters of a deque?

A seque? (Short for sesquible-ended queue.)

 

[Johann Klammer]

question

What do you call three-quarters of a deque?

e.g.

add to front
add to back
remove from front

WANTED: to dequeue an element from Queue.
GOT: nothing happening

/* A queue implementation with the operations that I need:
* (1) Add an element to the front (head) of the queue
* (2) Remove an element from rear (tail) of the queue
* (2) remove an element with a unique ID (string constant)
* (3) compare 2 elements (string comparison)
* (4) print queue
*
* VERSION 0.0
*/

note: the remove from front is missing.

de-queue versus deque [pronounced deck]