CODEWITHSUNDEEP
cpointersqueue
user2336315
user2336315

Reputation: 16067

How to dequeue en element from my custom queue

As an exercise, I'm trying to create a basic queue. I've got a problem in my deQueue method.

#include<stdio.h>

typedef int Task;
typedef struct QueueNode_ QueueNode;
typedef struct TQueue_ TQueue;

struct QueueNode_ {
    QueueNode* next;
    Task task;
};

struct TQueue_ {
    QueueNode* first;
    QueueNode* last;
};

TQueue* initializeQueue(){
    TQueue* queue = NULL;
    queue = malloc(sizeof(TQueue));
    queue->first = NULL;
    queue->last = NULL;
    return queue;
}

void enQueue(TQueue* q, Task t){
    if(q->first == NULL){
       q->first = malloc(sizeof(QueueNode));
       q->first->task = t;
       q->first->next = NULL;
       q->last = q->first;
    } else {
        QueueNode* node = malloc(sizeof(QueueNode));
        node->next = q->last;
        node->task = t;
        q->last = node;
    }
}

void printQueue(TQueue* q){
    QueueNode* node = q->last;
    printf("LAST->");
    while(node != NULL){
        printf("%d->", node->task);
        node = node->next;
    }
    printf("FIRST\n");
}

QueueNode* deQueue(TQueue* q){
    QueueNode* temp = q->first;
    QueueNode* newFirst = q->last;
    q->first = NULL;
    while(newFirst != NULL){
        newFirst = newFirst->next;
    }
    q->first = newFirst;
    return temp;
}

int main(){
    TQueue* queue = initializeQueue();
    enQueue(queue, 1);
    enQueue(queue, 2);
    printQueue(queue);
    QueueNode* node = deQueue(queue);
    printf("%d\n", node->task);
    printQueue(queue);
    return 0;
}

I expected my deQueue method to remove the head of my queue. But that's not the case apparently.

Here's the output:

LAST->2->1->FIRST
1
LAST->2->1->FIRST

I suspect my deQueue method to not replace the head of the queue with the second element but I though I was doing this with q->first = newFirst;, so I'm a bit stuck.

Just if it's not clear I would expect it to print:

LAST->2->1->FIRST
1
LAST->2->FIRST

Upvotes: 1

Views: 127

Answers (1)

Stefan Falk
Stefan Falk

Reputation: 25377

You might could do it like this:

QueueNode* deQueue(TQueue* q){
    QueueNode *tmp = q->last;

    while(tmp->next != q->first) {
        tmp = tmp->next;
    }
    // new first is now the old second element
    q->first = tmp;

    // new firsts' next still points at 
    // old first so we free that memory here
    free(q->first->next);
    q->first->next = NULL;

    return tmp;
}

Don't forget to free your memory.

You can test it here: http://www.compileonline.com/compile_c_online.php

Upvotes: 1

Related Questions