C, How to Remove Element From Queue?

Question

Update: we believe to find some bugs in both solutions , you are invited to share your ideas too :)

I was trying to implement my own data structure which combines list with queue in C.

my data structure has 2 pointers, front which points to the oldest member in the queue and rear which points to the newly added member which each member points to the one which got inserted after it.

For example if I insert 1 then 2 then 3, I will have:

NULL <-3 <- 2 <- 1 // 1 is front and 3 is rear.

Now I wanted to support removing element from this DS so I starting imeplemnting it and descovvered tens of edge cases like:

1. if the member is the front then change the front for DS and free the member, BUT if the front is null now then change rear to null too or the other code won't work as expected.

2. if the member is in middle release it then go back to prev member and update its next But this seems really hard

3. nearly the same for the rear member except we need to update rear now and only change the pointer to the element to its right (NULL is to its left)

How am I supposed to do something like this?

I already had tens of ideas and implementation for days but simply all failed or I did something really bad making the run time complexity much higher or I wrote 170 lines which had contradictions and left unfinished conditions (by using 2 pointers).

Any help please implementing this?

struct queue_node
{
    int key;
    struct queue_node *next;
};

struct queue
{
    int queue_size;
    struct queue_node *front, *rear;
};

int requeue(struct queue *q, int val)
{
    struct queue_node *tmp = q->front;
    while (tmp!=NULL)
    {
        if (tmp->key==val)
        {
            if (tmp==q->front)
            {
                q->front=tmp->next;
                if (q->front == NULL)
                {
                    q->rear = NULL;
                }
                free(tmp);
            }else if (tmp == q->rear)
            {

            }
            return 0; // found
        }
        tmp=tmp->next;
    }
    return -1; // not found
}

Answer 1

The function can be defined the following way

int requeue( struct queue *q, int val )
{
    struct queue_node **current = &q->front;
    struct queue_node *prev = NULL;

    while ( *current && ( *current )->key != val )
    { 
        prev = *current;
        current = &( *current )->next;
    }

    int success = *current == NULL ? -1 : 0;

    if ( success == 0 )
    {
        struct queue_node *tmp = *current;
        *current = ( *current )->next;
        free( tmp );
        --q->queue_size;            

        if ( *current == NULL ) q->rear = prev;
    }

    return success;
}

Here is a demonstrative program.

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

struct queue_node
{
    int key;
    struct queue_node *next;
};

struct queue
{
    int queue_size;
    struct queue_node *front, *rear;
};

int requeue( struct queue *q, int val )
{
    struct queue_node **current = &q->front;
    struct queue_node *prev = NULL;

    while ( *current && ( *current )->key != val )
    { 
        prev = *current;
        current = &( *current )->next;
    }

    int success = *current == NULL ? -1 : 0;

    if ( success == 0 )
    {
        struct queue_node *tmp = *current;
        *current = ( *current )->next;
        free( tmp );
        --q->queue_size;            

        if ( *current == NULL ) q->rear = prev;
    }

    return success;
}


int push( struct queue *q, int key )
{
    struct queue_node *node = malloc( sizeof( struct queue_node ) );
    int success = node != NULL;
    
    if ( success )
    {
        node->key = key;
        node->next = NULL;
        
        if ( q->rear == NULL )
        {
            q->front = q->rear = node;
        }
        else
        {
            q->rear = q->rear->next = node;
        }

        ++q->queue_size;            
    }
    
    return success;
}

void display( const struct queue *q )
{
    for ( struct queue_node *current = q->front; current; current = current->next )
    {
        printf( "%d -> ", current->key );
    }
    
    puts( "null" );
}

int main(void) 
{
    struct queue q = { .front = NULL, .rear = NULL };
    
    push( &q, 1 );
    push( &q, 2 );
    push( &q, 3 );
    push( &q, 4 );
    
    display( &q );
    
    requeue( &q, 4 );

    display( &q );

    push( &q, 4 );

    display( &q );

    requeue( &q, 1 );

    display( &q );

    requeue( &q, 3 );

    display( &q );

    requeue( &q, 4 );

    display( &q );

    requeue( &q, 2 );

    display( &q );

    push( &q, 1 );
    push( &q, 2 );
    push( &q, 3 );
    push( &q, 4 );
    
    display( &q );
    
    return 0;
}

The program output is

1 -> 2 -> 3 -> 4 -> null
1 -> 2 -> 3 -> null
1 -> 2 -> 3 -> 4 -> null
2 -> 3 -> 4 -> null
2 -> 4 -> null
2 -> null
null
1 -> 2 -> 3 -> 4 -> null

If for testing to add a call of the function printf to this code snippet within the function requeue

if ( success == 0 )
{
    struct queue_node *tmp = *current;
    *current = ( *current )->next;
    printf( "tmp->key == %d, tmp == %p\n", tmp->key, ( void * )tmp );
    free( tmp );
    --q->queue_size;            

    if ( *current == NULL ) q->rear = prev;
}

Then the output of the demonstrative program can look like

1 -> 2 -> 3 -> 4 -> null
tmp->key == 4, tmp == 0x55b55f9e02c0
1 -> 2 -> 3 -> null
1 -> 2 -> 3 -> 4 -> null
tmp->key == 1, tmp == 0x55b55f9e0260
2 -> 3 -> 4 -> null
tmp->key == 3, tmp == 0x55b55f9e02a0
2 -> 4 -> null
tmp->key == 4, tmp == 0x55b55f9e02c0
2 -> null
tmp->key == 2, tmp == 0x55b55f9e0280
null
1 -> 2 -> 3 -> 4 -> null

Answer 2

typedef struct queue_node
{
    int key;
    struct queue_node *next;
}node;

typedef struct 
{
    size_t size;
    node *head;
    node *tail;
}queue;

node *append(queue *q, int key)
{
    node *n = malloc(sizeof(*n));
    node *c = q -> head;
    if(n)
    {
        if(!q -> head) q -> head = n;
        else
        {
            while(c -> next) c = c -> next;
            c -> next = n;
        }
        n -> key = key;
        n -> next = NULL;
        q -> size++;
        q -> tail = n;
    }
    return n;
}

int removenode(queue *q, int key)
{
    node *n = q -> head, *p = q -> head;
    int result = 0;
    while(n)
    {
        if(n -> key == key)
        {
            if(n == p)
            {
                q -> head = n -> next;
                if(!n -> next) q -> tail = n;
            }
            else
            {
                p -> next = n -> next;                
                if(!p -> next) q -> tail = p;
            } 
            free(n);
            q -> size--;
            result = 1;
            break;
        }
        if(p != n) p = p -> next;
        n = n -> next;
    }
    return result;
}

void printqueue(queue *q)
{
    node *n = q -> head;
    printf("The queue:\n");
    while(n)
    {
        printf("Node key = %d\n", n -> key);
        n = n -> next;
    }
    printf("--------------\n");
    if(q -> head) printf("Head key: %d, Tail key: %d, Queue size: %zu\n -------------\n\n", q -> head -> key, q -> tail -> key, q -> size);
    else printf("Queue empty\n------------\n\n");
}

int main(void)
{
    queue q = {0,};
    append(&q,1);
    append(&q,2);
    append(&q,3);
    append(&q,4);
    printqueue(&q);
    removenode(&q,3);
    printqueue(&q);
    removenode(&q,1);
    printqueue(&q);
    removenode(&q,4);
    printqueue(&q);
    removenode(&q,2);
    printqueue(&q);

}

Result:

The queue:
Node key = 1
Node key = 2
Node key = 3
Node key = 4
--------------
Head key: 1, Tail key: 4, Queue size: 4
 -------------

The queue:
Node key = 1
Node key = 2
Node key = 4
--------------
Head key: 1, Tail key: 4, Queue size: 3
 -------------

The queue:
Node key = 2
Node key = 4
--------------
Head key: 2, Tail key: 4, Queue size: 2
 -------------

The queue:
Node key = 2
--------------
Head key: 2, Tail key: 2, Queue size: 1
 -------------

The queue:
--------------
Queue empty
------------

Program demo