c - 队列的 pop() 中的内存泄漏

Question

我的pop 功能似乎没有正常工作。基本上，我的队列 有一个指向第一个和最后一个元素的指针。

我的 pop 函数首先释放第一个元素并将其分配给 NULL。

然后它每次都使用指针curr 到达下一个元素，直到找到NULL。

最后，我队列中的第一个指针被分配给 prev，它指向我的 curr 达到 null 之前的最后一个元素。

#include <stdlib.h>

struct Queue {
    struct Node* first;
    struct Node* last;
};

struct Node {
    Item val;
    struct Node* next;
};


void initQueue (struct Queue **queue){
    (*queue) = malloc(sizeof(struct Queue));
    (*queue)->first = NULL;
    (*queue)->last = NULL;
}

struct Node* createNewNode(){
    struct Node *newNode;
    newNode = malloc(sizeof(struct Node));
    newNode->next = NULL;

    return newNode;
}



void push (Item val, struct Queue *queue){
    struct Node* newNode = createNewNode();
    newNode->val = val;


    if(queue->first == NULL){
        queue->first = newNode;
        queue->last = newNode;
    }

    else{
        newNode->next = queue->last;
        queue->last = newNode;
    }
}

void pop(struct Queue *queue){

    struct Node* curr = queue->last;
    struct Node* prev = queue->last;


    free(queue->first);
    queue->first = NULL;

    while(curr != NULL){
        prev = curr;
        curr = curr->next;
    }

    queue->first = prev;

}

Answer 1

要从列表的前面弹出，只需将 first 指向 first->next。

void pop(struct Queue *queue)
{
    if (NULL != queue->first) {
        struct Node *first = queue->first;
        // Update first ptr
        queue->first = queue->first->next;
        free(first);
        // Only need to update tail if list is empty
        if (NULL == queue->first) {
            queue->last = NULL;
        }
    }
}

编辑 根据您的评论，您似乎没有看到我在做什么，所以这里有一个例子。

假设队列是这样的:

queue->first
↓
A → B → C → D ← queue->last

首先，创建一个临时指针并让它指向queue->first。然后移动queue->first，使其指向queue->first->next。该列表现在如下所示:

queue->first
↓
A → B → C → D ← queue->last
↑
首先(临时变量)

然后，删除临时变量，列表为:

queue->first
↓
B → C → D ← queue->last

EDIT 2 我还注意到您的 push 功能不正确。在队列中，您将新项目添加到列表的末尾并从前面取出项目(FIFO - 先进先出)。就像人们排队看表演一样。 第一个到达那里并排队的人将第一个进入剧院。而最后到达的人排在队伍的后面。所以 push 应该是:

void push (Item val, struct Queue *queue){
    struct Node* newNode = createNewNode();
    newNode->val = val;

    if(queue->first == NULL) {
        queue->first = newNode;
        queue->last = newNode;
    }
    else{
        queue->last->next = newNode;  // Add to END of list
        queue->last = newNode;
    }
}