在C中使用链表实现队列

Question

这段代码是用C语言用链表实现队列和一些操作。我得到意外的输出，尤其是“删除前面的项目后：”这一行，但我不知道为什么。

这是我的代码：

// C program to implement linked list queue
#include <stdio.h>
#include <stdlib.h>

// Define a queue using linked list
typedef struct _Node {
    int data;
    struct _Node *next;
}Node;

typedef struct _Queue {
    Node *pFront, *pBack;
    int size;
}Queue;

// Initialize queue
Queue *init (void) {
    Queue *q = malloc(sizeof(*q));
    if (q) {
    q->size = 0;
    q->pFront = q->pBack = NULL;
    }
    return q;
}

// Check if queue is empty
int isEmpty (Queue q) {
    return (q.pFront == NULL);
}

// Length of train
int Length(Queue *q) {
    return q->size;
}

// Add new item
void enqueue (Queue *q, int val)
{
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = val;
    p->next = NULL;

    // If queue is empty
    if (q->pFront == NULL)
        q->pFront = q->pBack = p;

    // If queue has at least 1 element
    else {
        p->next = q->pBack;
        q->pBack = p;
    }
    q->size++;
}

// Remove item
int dequeue (Queue *q)
{
    if (isEmpty(*q))
        return 0;
    else {
        if (q->size == 1) {
            q->pFront = q->pBack = NULL;
            q->size--;
        }
        else {
            Node *p = q->pBack;
            while (p->next != q->pFront)
                p = p->next;
            q->pFront = p;
            q->pFront->next = NULL;
            q->size--;
        }
    }
    return 1;
}

// Display queue
void display(Queue *q) {
    Node *p = q->pBack;
    while (p != NULL) {
        printf("%d\t", p->data);
        p = p->next;
    }
}

// Free all memory used by the stack
void freeMemory(Queue *q) {
    Node* p = q->pFront;
    Node* next;

    while (p != NULL) {
        next = p->next;
        free(p);
        p = next;
    }

    q->pFront = NULL;
    q->size = 0;
}

int main()
{
    Queue *q;
    q = init();
    if (q)
    {
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    printf("Queue:\n");
    display(q);

    printf("\nAfter removing front item: %d", dequeue(q));
    display(q);

    printf("\nLength of the queue after all modification: %d", Length(q));

    freeMemory(q);
    return 0;
    }
}

意外的输出： ** 队列： 10 20 30 删除前面的项目后：110 20 全部修改后队列长度：2 **

Answer 1

您的输出会误导您，因为您没有始终如一地在末尾打印换行符。特别是这里：

    printf("\nAfter removing front item: %d", dequeue(q));
    display(q);

...打印

dequeue()

的返回值（始终为 1 或 0），然后打印剩余队列项的值，不带任何前导空格。你的

110 20

因此可以分解为 1（

dequeue()

的返回值）、10（队列项）、20（队列项）。

这是错误的，因为第一个出队的项目应该是第一个入队的项目（10）。 但这不是你的程序为我打印的内容。当我运行你的程序时，我得到

After removing front item: 130  20
Length of the queue after all modification: 2

这表明正确的项目已被删除。然而，我天真的期望是，队列将按照元素出列的顺序打印，这与程序发出的顺序相反。

至少，将那些缺少的换行符添加到程序的输出中。还要验证

display()

所需的输出顺序，并根据需要进行修复。