C语言——队列的实现

        队列按照先进先出（FIFO，First In First Out）的原则管理数据。这意味着最先进入队列的元素会被最先移出，类似于排队等候服务的情况。队列通常有两个主要操作：入队（enqueue），将元素添加到队列的尾部；出队（dequeue），从队列的头部移除元素。

        如果用顺序表实现队列，在删除队头数据时，需要后面的数据覆盖前面的数据，比较麻烦，所以采用链表，头删尾插代替出队和入队。但是如果用链表实现的话，寻找队尾入队还需要一直 ->next ，所以干脆我们就记录下头指针和尾指针方便头山尾插。

首先就是定义每个节点的结构体和定义队列的结构体：

struct QueueList {int val;struct QueueList* next;
};
struct Queue {struct QueueList* head;struct QueueList* tail;
};

        这里用QueueNode命名第一个结构体更好，因为我们要记录头尾指针，所以Queue结构体就有头尾两个指针。

接下来是初始化函数和销毁函数；

void QueueInit(struct Queue* list) {list->head = NULL;list->tail = NULL;
}
void QueueDes(struct Queue* list) {while (list->head!=list->tail){struct QueueList* next = list->head->next;free(list->head);list->head = next;}free(list->head);list->head = list->tail = NULL;
}

        初始化函数让list的头指针和尾指针都置为空，销毁函数，如果头尾指针相等，有两种情况，一种是空队列，这时 free(NULL) ，还可以是只有一个元素，头尾指针都指向这个元素，这时free掉，然后指针置空，所以不会有野指针或者free错误的情况。

然后是入队出队函数：

void QueuePushBack(struct Queue* list,int num) {if (list->head == list->tail && list->head == NULL) {list->head = list->tail = malloc(sizeof(struct QueueList));list->head->val = num;list->tail->next = NULL;}else if (list->head == list->tail) {list->tail = malloc(sizeof(struct QueueList));list->tail->val = num;list->tail->next = NULL;list->head->next = list->tail;}else {struct QueueList* tail_pre = list->tail;list->tail = malloc(sizeof(struct QueueList));list->tail->val = num;list->tail->next = NULL;tail_pre->next = list->tail;}
}
int QueueFrontPop(struct Queue* list) {struct QueueList* new_head = list->head->next;int val = list->head->val;free(list->head);list->head = new_head;return val;
}

        对于尾插函数，头尾指针相等时有可能是空队列也有可能是只创建了一个元素，所以要分开讨论，简单逻辑就是让尾节点的next指向新开辟的节点，然后更新尾指针使新开辟的节点变为尾指针，最后让尾节点的next置为NULL。

        对于头删Pop函数，就是先存头节点下一个节点的地址然后free掉头节点，更新头指针，返回数值。

最后是打印函数方便我们观察：

void QueuePrint(struct Queue* list) {struct QueueList* cur = list->head;while (cur != NULL) {printf("%d ", cur->val);cur = cur->next;}
}

这就是文章的全部内容，希望对你有所帮助，如有错误欢迎评论。