为什么我的队列无限循环？

Question

我自己实现了队列 ADT，但我在某个地方搞砸了一些东西，我无法理解我在这里做错了什么。

这是queue.h供参考：

typedef struct op_queue *Queue;

Queue crea_queue();
void enqueue(Queue queue, int num);
int dequeue(Queue queue);
int isQueueEmpty(Queue queue);
int queueSize(Queue queue);
int head(Queue queue);

这是队列。c

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

typedef struct Item{
    int num;
    struct Item *next;
} Item;

Item *crea_item(int num){
    Item *new = malloc(sizeof(Item));
    if (!new){
        printf("ERROR ALLOCATING");
        exit(-1);
    }

    new->num=num;
    new->next=NULL;
    return new;
}

struct op_queue{
    Item *head;
    Item *tail;
    int size;
};

int head(Queue queue){
    return queue->head->num;
}


Queue crea_queue(){
    Queue new = malloc(sizeof(struct op_queue));
    if (!new){
        printf("ERROR ALLOCATING");
        exit(-1);
    }
    new->head = NULL;
    new->tail = NULL;
    new->size = 0;
    return new;
};


void enqueue(Queue queue, int num){
    Item *temp = crea_item(num);
    if (queue->tail == NULL){
        queue->tail = temp;
    }
    if (queue->head == NULL){
        queue->head = temp;
    }
    else{
        Item *foo = queue->head;
        queue->head = temp;
        temp->next = foo;
    }
    queue->size++;
}

Item *recursive_last(Item *item){
    if (item->next != NULL){
        return recursive_last(item->next);
    }
    return item;
}


Item *find_last(Queue queue){
    Item *result = NULL;
    if (queue->head != NULL){
        result = recursive_last(queue->head);
    }
    return result;
}


int dequeue(Queue queue){
    Item *temp = queue->tail;
    int result = temp->num;
    free(queue->tail);
    queue->tail = find_last(queue);
    queue->size--;
    return result;
}


int isQueueEmpty(Queue queue){
    return (queue->head==NULL);
}

int queueSize(Queue queue){
    return queue->size;
}

出于测试目的，这是 main.c:

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


int main(void){
    Queue foo = crea_queue();
    enqueue(foo, 11);
    enqueue(foo, 12);
    dequeue(foo);
    printf("you did it!!");
    return 0;
}

我尝试检查代码几次，但无济于事......问题可能出在排队函数中，也许是临时的？

Answer 1

太复杂了。如果您存储尾部和头部，则不需要迭代。

typedef struct Item{
    int num;
    struct Item *next;
} Item;

typedef struct op_queue{
    Item *head;
    Item *tail;
    size_t size;
}Queue;

Queue *push(Queue *q, int val)
{
    size_t newsize = q ? q -> size + 1 : 1;
    if(!q)
    {
        q = calloc(1, sizeof(*q));
    }
    if(q)
    {
        Item *i = calloc(1, sizeof(*i));
        if(i)
        {
            i -> num = val;
            if(!q -> head)
            {
                q -> head = i;
                q -> tail = i;
                i -> next = NULL;
            }
            else
            {
                q -> tail -> next = i;
                q -> tail = i;
            }
        }
        q -> size = newsize;
    }
    return q;
}

int pop(Queue *q, int *val)
{
    int result = -1;
    Item *i;
    if(q)
    {
        if(q -> head)
        {
            i = q -> head;
            *val = i -> num;
            result = 0;
            q -> head = i -> next;
            q -> size--;
            free(i);
        }
    }
    return result;
}

int main(void){
    Queue *foo = push(NULL, 11);
    int val;
    if(foo)
    {
        push(foo, 12);
        push(foo, 13);
        while(!pop(foo, &val))
            printf("The val is %d\n", val);
    }
    free(foo);
 }