https://blog.csdn.net/kxcfzyk/article/details/31728179

隊列并不是很復雜的數據結構，但是非常實用，這里實現一個隊列是因為在我的另一篇博客非常精簡的Linux線程池實現中要用到。

?

隊列API定義如下：

?

1. //queue.h

2. ?

3. #ifndef QUEUE_H_INCLUDED

4. #define QUEUE_H_INCLUDED

5. ?

6. typedef struct queue *queue_t;

7. ?

8. queue_t queue_create();

9. ?

10. int queue_isempty(queue_t q);

11. ?

12. void* queue_enqueue(queue_t q, unsigned int bytes);

13. ?

14. void* queue_dequeue(queue_t q);

15. ?

16. void queue_destroy(queue_t q);

17. ?

18. #endif //QUEUE_H_INCLUDED

隊列API提供的功能有：創建隊列，判斷隊列是否為空，入隊，出隊，銷毀隊列。這個隊列是通用的，不針對特定數據類型，它里面存儲的元素是void*類型的指針。注意這個隊列跟普通隊列的入隊操作有所不同。普通隊列的入隊操作通常如下：

?

1. struct type *p;

2. p = malloc(sizeof(struct type));

3. p->a = ...;

4. p->b = ...;

5. p->c = ...;

6. ...

7. queue_enqueue(q, p);

而這里的入隊操作簡化了流程：

?

1. struct type *p;

2. p=queue_enqueue(q, sizeof(struct type));

3. p->a = ...;

4. p->b = ...;

5. p->c = ...;

6. ...

另外雖然隊列元素（指針）所指向的內存空間是在入隊操作時由隊列分配的，但是隊列元素出隊以后，隊列并不負責元素所指向內存空間的釋放，隊列使用者應該自己手動釋放內存。

?

隊列的實現如下：

?

1. //queue.c

2. ?

3. #include "queue.h"

4. #include <stdlib.h>

5. ?

6. struct node {

7. void *element;

8. struct node *next;

9. };

10. ?

11. struct queue {

12. struct node front;

13. struct node *tail;

14. };

15. ?

16. queue_t queue_create() {

17. queue_t q;

18. q=(queue_t)malloc(sizeof(struct queue));

19. q->front.element=NULL;

20. q->front.next=NULL;

21. q->tail=&q->front;

22. return q;

23. }

24. ?

25. int queue_isempty(queue_t q) {

26. return &q->front==q->tail;

27. }

28. ?

29. void* queue_enqueue(queue_t q, unsigned int bytes) {

30. q->tail->next=(struct node*)malloc(sizeof(struct node));

31. q->tail->next->element=malloc(bytes);

32. q->tail->next->next=NULL;

33. q->tail=q->tail->next;

34. return q->tail->element;

35. }

36. ?

37. void* queue_dequeue(queue_t q) {

38. struct node *tmp=q->front.next;

39. void *element;

40. if(tmp==NULL) {

41. return NULL;

42. }

43. element=tmp->element;

44. q->front.next=tmp->next;

45. free(tmp);

46. if(q->front.next==NULL) {

47. q->tail=&q->front;

48. }

49. return element;

50. }

51. ?

52. void queue_destroy(queue_t q) {

53. struct node *tmp, *p=q->front.next;

54. while(p!=NULL) {

55. tmp=p;

56. p=p->next;

57. free(tmp);

58. }

59. free(q); // 感謝@Toudsour指正

60. }

應用程序使用隊列時只需要包含queue.h頭文件，并在編譯時將queue.c一起編譯就行了。因為隊列的聲明和實現是嚴格分離的，包含queue.h的應用程序無法也不應該通過隊列指針直接訪問隊列結構體的成員。