CODEWITHSUNDEEP
cdata-structures
Mr.Mountain
Mr.Mountain

Reputation: 883

Pointer will not show to the next entry in a queue

I'm trying to build a simple queue but I'm stuck. I will explain it with the datastructures

typedef struct location_tag {
    int x;
    int y;
} Location;

typedef struct QueueNode{
    struct QueueNode *next;
    Location location;
}QueueNode;

typedef struct Queue{
    struct QueueNode *begin;
    struct QueueNode *end;
    int size;
}Queue;

The queue will hold a pointer to the first and last element in it. Every node knows it's next. Now I implemented enqueue-/dequeue-operations:

void enqueue(Location l, Queue *q) {
    printf("--------ENQUEUE--------\n");
    QueueNode newEntry = { NULL, l };

    if (q->size == 0) {
        q->end = &newEntry;
        q->begin = &newEntry;
    } else {
        newEntry.next = q->begin;
        q->begin = &newEntry;
    }

    q->size++;
    printQueue(q);
}

QueueNode* dequeue(Queue *q) {
    printf("--------DEQUEUE--------\n");
    QueueNode* node = q->end;
    q->size--;

    QueueNode *currentNode = q->begin;
    for (int z = 1; z < q->size; ++z) {
        currentNode = currentNode->next;
    }
    q->end = currentNode;
    printQueue(q);

    return node;
}

void printQueue(Queue* q) {
    QueueNode *currentNode = q->begin;

    for (int z = 0; z < q->size; ++z) {
        printf("Location(x=%d|y=%d) ==next==> ", currentNode->location.x,
                currentNode->location.y);
        currentNode = currentNode->next;
    }
    printf("\n\n");

}

This is a FIFO-queue. So the first entry will be the first when dequeue is called. Here's a little main with tests.

int main(void){
    Queue queue = { NULL, NULL, 0 };
    queuePtr = &queue;

    Location l1 = { 1, 0 };
    Location l2 = { 2, 0 };
    Location l3 = { 3, 0 };
    enqueue(l1, queuePtr);
    enqueue(l2, queuePtr);
    enqueue(l3, queuePtr);

    while (queue.size != 0) {
        nodePtr = dequeue(queuePtr);
    }
return 0;
}

What is the question? When I put an new entry in my queue the pointer to the next element will point to the node itselft. Here's an example output:

--------ENQUEUE-------- Location(x=1|y=0) ==next==>

--------ENQUEUE-------- Location(x=2|y=0) ==next==> Location(x=2|y=0) ==next==>

--------ENQUEUE-------- Location(x=3|y=0) ==next==> Location(x=3|y=0) ==next==> Location(x=3|y=0) ==next==>

I don't understand this behaviour. I guess this is wrong newEntry.next = q->begin); ? Perhaps you can help me. Thank you.

Upvotes: 0

Views: 103

Answers (1)

NPE
NPE

Reputation: 500367

The main issue is that newEntry lives on the stack:

void enqueue(Location l, Queue *q) {
    printf("--------ENQUEUE--------\n");
    QueueNode newEntry = { NULL, l };

    if (q->size == 0) {
        q->end = &newEntry;
        ...

Once enqueue() returns, newEntry ceases to exist, and you'll have undefined behaviour the moment you try to dereference any of the pointers to newEntry.

Upvotes: 1

Related Questions