我必须为更大的项目实现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始终返回相同的值...
您是否知道问题可能来自何处？我尝试使用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;
}
}
在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