Мне нужно реализовать интерфейс очереди 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;
}
}