c - 实现带有喜欢列表的队列

Question

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

typedef struct node{
    int info;
    struct node * next;
}Node;

typedef Node * List;

struct queue{
    int size;
    List tail;
    List head;
};

typedef struct queue *Queue;


/* post: creates an empty queue */
Queue initqueue(){
    Queue q;
    q = malloc(sizeof(struct queue));
    q->tail = q->head = NULL;
    q->size = 0;
    return q;
}

/*post: returns 1 if the queue is empty 0 otherwise  */
int queueempty(Queue q){
    return (q->head) == NULL ? 1 : 0;
}

/*post: inserts an element at the end */
void enqueue(Queue q, int elem){
    List temp = (List)malloc(sizeof(Node));
    temp->info = elem;


    if(q->head == NULL){
        temp->next = q->head ;
        q->head = temp;
    }else{
        temp->next = q->tail;
        q->tail = temp;
    }
    (q->size)++;
}

/*pre: queue not empty */
/*post: returns and removes the first element of the queue */

int dequeue(Queue q){
    int ris;
    List temp;

    temp = q->head;
    q->head = q->head->next;
    ris = temp->info;
    free(temp);
    (q->size)--;

    return ris;
}

/*pre: queue not empty */
/*post: returns the first element of the queue */
int first(Queue q){
    return q->head != NULL ? q->head->info : -1;
}

/*post: returns the number of elements in the queue */
int sizequeue(Queue q){
    return q->size;
}

这就是我尝试实现带有喜欢列表的队列的方法。问题是，每当我使用 dequeue() 函数时，我的 q->head 指针就会变为 NULL，因此我会丢失这行代码周围发生的头:

q->head = q->head->next;

但我不确定这行是否错误，或者 enqueue() 函数是否错误，因为 q->head 和 q->tail 应该指向同一个链表，但我想嘿不所以我'我测试了一下，这就是我得到的:

如果我在非空队列上执行 dequeue()，first() 函数将返回 -1(q->head == NULL) 然后，如果我执行 enqueue(q,10)，first() 函数将返回返回 10 作为队列的头部，因此 enqueue() 将元素放在队列的前面而不是末尾，我似乎无法理解出了什么问题。

如果有人可以帮助我整理我的代码，那将非常有帮助，谢谢。

Answer 1

1) 添加第一个元素时不更新 tail

2)添加其他元素的代码错误。

试试这个

void enqueue(Queue q, int elem){
    List temp = (List)malloc(sizeof(Node));
    temp->info = elem;
    temp->next = NULL;   // Always set next to NULL as you add to the tail


    if(q->head == NULL){
        q->head = temp;
        q->tail = temp;        // Also update tail
    }else{
        q->tail->next = temp;  // Make current tail element link the new element
        q->tail = temp;        // Update the tail to the new element
    }
    (q->size)++;
}