C语言实现队列

原理：

通过单链表实现的队列，队列就是一个尾插头删的单链表，先实现一个链表，再实现一个队列包括队头指针和队尾指针
图

 1 #ifndef Queue_h
 2 #define Queue_h
 3 
 4 #include <stdio.h>
 5 
 6 typedef int QDataType;        //数据类型
 7 
 8 typedef struct ListNode        //通过链表实现的
 9 {
10     QDataType _data;
11     struct ListNode* _pNext;
12 }ListNode,*pListNode;
13 
14 typedef struct Queue
15 {
16     pListNode _pHead;        //头指针
17     pListNode _pTail;        //尾指针
18 }Queue;
19 
20 void QueueInit(Queue* q);        //初始化
21 void QueuePush(Queue* q, QDataType d);//进队列（尾插）
22 void QueuePop(Queue* q);        //出队列（头删）
23 int QueueSize(Queue* q);        //求队列大小
24 int QueueEmpty(Queue* q);        //队列判空
25 QDataType Front(Queue* q);        //获取队头元素
26 QDataType Back(Queue* q);        //获取队尾元素
27 
28 #endif /* Queue_h */

View Code

 1 #include "Queue.h"
 2 #include <assert.h>
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 
 6 pListNode BuyNode(QDataType d)
 7 {
 8     pListNode new = malloc(sizeof(ListNode));
 9     new->_data = d;
10     new->_pNext = NULL;
11     return new;
12 }
13 
14 void QueueInit(Queue* q)
15 {
16     assert(q);
17     q->_pHead = BuyNode(0);
18     q->_pTail =q->_pHead;
19 }
20 
21 void QueuePush(Queue* q, QDataType d)
22 {
23     assert(q);
24     q->_pTail->_pNext = BuyNode(d);
25     q->_pTail = q->_pTail->_pNext;
26     
27 }
28 
29 void QueuePop(Queue* q)
30 {
31     pListNode dNode = q->_pHead->_pNext;
32     if (dNode)
33     {
34         q->_pHead->_pNext = dNode->_pNext;
35         if (q->_pHead->_pNext == NULL) {
36             q->_pTail = q->_pHead;
37         }//如果只有一个元素，删完后ptail会悬空
38         free(dNode);
39     } 
40 }
41 
42 int QueueSize(Queue* q)
43 {
44     assert(q);
45     pListNode pre = q->_pHead->_pNext;
46     int count = 0;
47     while (pre)
48     {
49         count++;
50         pre = pre->_pNext;
51     }
52     return count;
53 }
54 int QueueEmpty(Queue* q)
55 {
56     return NULL == q->_pHead->_pNext;
57     
58 }
59 QDataType Front(Queue* q)
60 {
61     return q->_pHead->_pNext->_data;
62 }
63 QDataType Back(Queue* q)
64 {
65     return q->_pTail->_data;
66 }