队列接口

Question

我必须为一个更大的项目实现一个 FIFO 队列接口。队列需要处理任何类型的数据，因此我决定使用 void* 指针作为队列节点的值，并使用双链表。每个节点都有一个value、一个prev和一个next.

为了更好理解，请注意front指的是队列中的第一个节点，back是最后加入的节点。

我写了一个enqueue和一个dequeue函数，还有一个peek_back和一个peek_front function。

但是，当我运行在我的 main() 函数中进行一些测试时，看起来有些问题：

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

int main(){

    queue_t* q = init_queue();
    if(q == NULL){
        printf("Error: q not initialized properly\n");
        return 1;
    }

    //Test with a struct
    struct point {
       int    x;
       int    y;
    };

    for(int i = 1; i <= 3; i++){
        struct point p = {i,i};
        struct point* p_ptr = &p;
        enqueue(q, (void*) p_ptr);
        printf("One node added, front value: %i, back value: %i\n", ((struct point*)peek_front(q))->x, ((struct point*)peek_back(q))->x);
    }

    int result;
    int size;
    while(q->size > 0){
        result = *(int*) dequeue(q);
        size = q->size;
        printf("One node removed, value = %i. Size is now %i \n", result, size);
    }

    return 0;
}

输出为：

gcc main.c queue.c -o main.o -Wall -Werror
./main.o
One node added, front value: 1, back value: 1
One node added, front value: 2, back value: 2
One node added, front value: 3, back value: 3
One node removed, value = 3. Size is now 2 
One node removed, value = 3. Size is now 1 
One node removed, value = 3. Size is now 0

如您所见，enqueue 更改了队列的前端节点，尽管它不应该，并且 dequeue 总是 return 相同的值...

您知道问题出在哪里吗？我尝试使用 gdb 进行调试，但我真的很难发现问题所在。另外，我很高兴听到您对此队列的一般实现的反馈...欢迎任何建议，因为我只是 C 语言的初学者 ;)

这是我的 queue.h 头文件：

#ifndef QUEUE_H
#define QUEUE_H


typedef struct node{
  struct node* next;
  struct node* prev;
  void* value;
} node_t;

typedef struct queue{
  struct node* front;
  struct node* back;
  int size;
} queue_t;

queue_t* init_queue();
int enqueue(queue_t* q, void* val);
void* dequeue(queue_t* q);
int get_size(queue_t* q);
int is_empty(queue_t * q);
void* peek_front(queue_t * q);
void* peek_back(queue_t * q);

#endif

这是我的 queue.c 文件：

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

/*
 * Allocate memory and initialize a new queue with size = 0 and front = NULL
 * @return: initialized queue if succes, NULL if failed malloc
 */
queue_t* init_queue(){
    queue_t* newQueue = (queue_t*)malloc(sizeof(queue_t));
    if(!newQueue){
        printf("Malloc error in init_queue\n");
        return NULL;
    }
    newQueue->front = NULL;
    newQueue->back = NULL;
    newQueue->size = 0;

    return newQueue;
}

/*
 * Add a new node with value @val at the end (back) of the queue @q
 * @q: a valid queue (queue_t type)
 * @val: the value to be added
 * return 0 if success, -1 if failure
 */
int enqueue(queue_t* q, void* val){
    struct node *newNode = (struct node*) malloc(sizeof(struct node));
    if(!newNode) return  -1;
    newNode->value = val;

    if(q->size == 0){
        newNode->next = newNode;
        newNode->prev = newNode;
        q->front = newNode;
        q->back = newNode;
    }
    else{
        newNode->next = q->back;
        newNode->prev = q->front;
        q->back->prev = newNode;
        q->front->next = newNode;
        q->back = newNode;
    }

    q->size ++;

    return 0;
}

/*
 * Remove front node of queue @q and return its value
 * @q: a valid queue
 * @return: value of removed front node (int) if success
 *          NULL if empty queue
 */
void* dequeue(queue_t* q){
    if(q->size == 0){
        printf("Warning: empty queue\n");
        return NULL;
    }

    void* tbr = q->front->value; //to be returned

    if(q->size == 1){
        free(q->front);
        q->front = NULL;
    }else{
        struct node * old_front = q->front;
        old_front->prev->next = q->back;
        q->back->prev = old_front->prev;
        q->front = old_front->prev;
    }
    q->size--;

    return tbr;
}

/*
 * @q: a valid queue
 * @return: size of queue @q if q is not NULL
 *          -1 if q is NULL
 */
int get_size(queue_t* q){
    if(q != NULL){
        return q->size;
    }else{
        return -1;
    }
}

/* 
 * Check wether @q is empty or not
 * @q: a valid queue
 * @return: 1 if @q is empty, 0 otherwise
 */
int is_empty(queue_t * q){
    return get_size(q) == 0;
}

/*
 * Peek the value of front node of queue @q, but doesn't remove it
 * @q: a valid queue
 * @return: value of front node
 */
void* peek_front(queue_t * q){
    if (q->size == 0){
        printf("Peeking an empty queue\n");
        return NULL;
    }else{
        return q->front->value;
    }
}

/*
 * Peek the value of last node (last added, back of the tail) 
 * from queue @q, but doesn't remove it
 * @q: a valid queue
 * @return: value of last-added node (back)
 */
void* peek_back(queue_t * q){
    if (q->size == 0){
        printf("Peeking an empty queue\n");
        return NULL;
    }else{
        return q->back->value;
    }
}

Answer 1

在 main() 中，您这样做：

for(int i = 1; i <= 3; i++){
    struct point p = {i,i};    // HERE : automatic local inside loop
    struct point* p_ptr = &p;  // HERE : acquire the address of that local var
    enqueue(q, (void*) p_ptr); // HERE : store said address in the queue
    printf("One node added, front value: %i, back value: %i\n", ((struct point*)peek_front(q))->x, ((struct point*)peek_back(q))->x);
} // HERE : address stored is no longer valid.

动态分配是一种解决方案，而且相当简单。 Sans 错误检查是这样的：

for (int i = 1; i <= 3; i++) 
{
    struct point *p = malloc(sizeof *p);
    p->x = p->y = i;
    enqueue(q, p);
    printf("One node added, front value: %i, back value: %i\n", 
        ((struct point*)peek_front(q))->x, ((struct point*)peek_back(q))->x);
}


while (q->size > 0) {
    struct point *p = dequeue(q);
    printf("One node removed, value = (%i,%i). Size is now %i \n", p->x, p->y, q->size);
    free(p); // NOTE, freeing the dynamic memory we allocated during insertion.
}

free(q);

输出

One node added, front value: 1, back value: 1
One node added, front value: 1, back value: 2
One node added, front value: 1, back value: 3
One node removed, value = (1,1). Size is now 2
One node removed, value = (2,2). Size is now 1
One node removed, value = (3,3). Size is now 0

队列接口

Queue interface

c

queue

pointers

doubly-linked-list