本文共 1846 字，大约阅读时间需要 6 分钟。
队列并不是很复杂的数据结构，但是非常实用，这里实现一个队列是因为在我的另一篇博客中要用到。
队列API定义如下：
//queue.h
#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED
typedef struct queue *queue_t;
queue_t queue_create();
int queue_isempty(queue_t q);
void* queue_enqueue(queue_t q, unsigned int bytes);
void* queue_dequeue(queue_t q);
void queue_destroy(queue_t q);
#endif //QUEUE_H_INCLUDED
队列API提供的功能有：创建队列，判断队列是否为空，入队，出队，销毁队列。这个队列是通用的，不针对特定数据类型，它里面存储的元素是void*类型的指针。注意这个队列跟普通队列的入队操作有所不同。普通队列的入队操作通常如下：
struct type *p;
p = malloc(sizeof(struct type));
p->a = ...;
p->b = ...;
p->c = ...;
...
queue_enqueue(q, p);
而这里的入队操作简化了流程：
struct type *p;
p=queue_enqueue(q, sizeof(struct type));
p->a = ...;
p->b = ...;
p->c = ...;
...
另外虽然队列元素（指针）所指向的内存空间是在入队操作时由队列分配的，但是队列元素出队以后，队列并不负责元素所指向内存空间的释放，队列使用者应该自己手动释放内存。
队列的实现如下：
//queue.c
#include "queue.h"
#include <stdlib.h>
struct node {
void *element;
struct node *next;
};
struct queue {
struct node front;
struct node *tail;
};
queue_t queue_create() {
queue_t q;
q=(queue_t)malloc(sizeof(struct queue));
q->front.element=NULL;
q->front.next=NULL;
q->tail=&q->front;
return q;
}
int queue_isempty(queue_t q) {
return &q->front==q->tail;
}
void* queue_enqueue(queue_t q, unsigned int bytes) {
q->tail->next=(struct node*)malloc(sizeof(struct node));
q->tail->next->element=malloc(bytes);
q->tail->next->next=NULL;
q->tail=q->tail->next;
return q->tail->element;
}
void* queue_dequeue(queue_t q) {
struct node *tmp=q->front.next;
void *element;
if(tmp==NULL) {
return NULL;
}
element=tmp->element;
q->front.next=tmp->next;
free(tmp);
if(q->front.next==NULL) {
q->tail=&q->front;
}
return element;
}
void queue_destroy(queue_t q) {
struct node *tmp, *p=q->front.next;
while(p!=NULL) {
tmp=p;
p=p->next;
free(tmp);
}
free(q); // 感谢@Toudsour指正
}
应用程序使用队列时只需要包含queue.h头文件，并在编译时将queue.c一起编译就行了。因为队列的声明和实现是严格分离的，包含queue.h的应用程序无法也不应该通过队列指针直接访问队列结构体的成员。
转载地址：http://dwlii.baihongyu.com/