用单向链表实现队列

发现用链表实现必用数组容易多了：

• 初始化队列：创建一个指向队列节点的头指针
• 入队：创建一个新节点，将它添加到链表尾部，如果链表为空，让头指针指向该节点
• 出队：free 头指针指向第一个节点， 让头指针指向该节点的下一个节点， 然后返回该节点的值。
• 判断队列是否为空：如果头指针指向 NULL 则该队列是空队列。

纯C语言实现：

#include <stdio.h>
#include <malloc.h>
#define ERROR -1
#define bool int
#define Flase 0
#define True 1
#define elem_type int


typedef struct _node {
    elem_type data;
    struct _node* next;
} Node;

typedef struct q_node {
    Node* front;
    // Node* rear;  不需要
} Queue;

// 初始化
Queue* create_queue(void)
{
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    
    return q;
}

// 队列是否是空，链表可以一直申请内存一般不会满。
bool is_empty(Queue* q)
{
    return (q->front == NULL);
}

// 出队
elem_type delete_q(Queue* q)
{
    if (q->front != NULL){
        elem_type n;
        Node* p = q->front;     // 记录第一个节点的地址
        n = p->data;        // 记录第一个节点的值
        q->front = p->next;     // 更新头指针指向
        free(p);    // 释放内存
        
        return n;
    } else {
        return ERROR;
    }
}

// 入队
void add_q(Queue *q, elem_type x)
{
    Node *node = (Node*)malloc(sizeof(Node));
    node->data = x;
    node->next = NULL;
    
    // 将节点添加到链表尾部
    Node* last = q->front;
    if (last){
        // 寻找最后一个节点
        while (last->next){
            last = last->next;
        }
        // 添加
        last->next = node;
    } else {
        q->front = node;
    }
}

// 输出队列
void print(Queue* q)
{
    Node* p;
    for (p=q->front; p; p = p->next){
        printf("%d ", p->data);
    }
    printf("\n");
}

int main(void)
{
    Queue* Q = NULL;
    Q = create_queue();
    // 才创建的队列应为空
    if (is_empty(Q)){
        printf("队列为空\n");
    }
    int i = 0;
    // 入队 0 1 2 3 4
    while (i<5){
        add_q(Q, i++);
    }
    // 出队 0
    delete_q(Q);
    // 输出 1 2 3 4
    print(Q);
    return 0;
}