队列，又称为伫列（queue），计算机科学中的一种抽象资料型别，是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为）进行插入操作，在前端（称为）进行删除操作。
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
单链队列使用链表作为基本数据结构，所以不存在伪溢出的问题，队列长度也没有限制。但插入和读取的时间代价较高
1 // 定义单链队列的存储结构 2 typedef struct QNode { 3 int data; 4 QNode *next; 5 }QNode,*QNodePtr; 6 7 typedef struct LinkQueue{ 8 //队头 队尾 指针 9 QNodePtr front,rear; 10 }LinkQueue; 11 12 13 // 构造一个空队列Q 14 LinkQueue* Q_Init() { 15 //申请内存 16 LinkQueue* Q = (LinkQueue*)malloc(sizeof(LinkQueue)); 17 //如果 Q 为 NULL 说明 内存申请失败，结束程序 18 if (!Q) 19 exit(OVERFLOW); 20 //初始化头尾节点 指向相同地址 21 Q->front = Q->rear = (QNodePtr)malloc(sizeof(QNode)); 22 //如果 Q->front 为 NULL 说明 内存申请失败，结束程序 23 if (!Q->front) 24 exit(OVERFLOW); 25 Q->front->next = NULL; 26 return Q; 27 } 28 29 // 销毁队列Q(无论空否均可) 30 void Q_Destroy(LinkQueue *Q) { 31 while (Q->front) { 32 //将队尾指向队头下一个节点的地址（第1个节点） 33 Q->rear = Q->front->next; 34 //回收队头 35 free(Q->front); 36 //将队头指向队尾（相当于第1个节点变成了队头，然后依次第2个第3个、、、 37 //直到没有下一个节点，也就是 Q->front == NULL 的时候） 38 Q->front = Q->rear; 39 } 40 free(Q); 41 } 42 43 // 将Q清为空队列 44 void Q_Clear(LinkQueue *Q) { 45 QNodePtr p, q; 46 //将队尾指向队头点的地址 47 Q->rear = Q->front; 48 //取出第1个节点 49 p = Q->front->next; 50 //回收第1个节点 51 Q->front->next = NULL; 52 while (p) { 53 //将 q 指向 p（第1个节点） 54 q = p; 55 //将 p 指向 第2个节点 56 p = p->next; 57 //回收第2个节点 58 free(q); 59 } 60 } 61 62 // 若Q为空队列，则返回-1，否则返回1 63 int Q_Empty(LinkQueue Q) { 64 if (Q.front->next == NULL) 65 return 1; 66 else 67 return -1; 68 } 69 70 // 求队列的长度 71 int Q_Length(LinkQueue Q) { 72 int i = 0; 73 QNodePtr p; 74 p = Q.front; 75 //遍历队列中的节点，直到队尾等于队头 76 while (Q.rear != p) { 77 i++; 78 p = p->next; 79 } 80 return i; 81 } 82 83 // 打印队列中的内容 84 void Q_Print(LinkQueue Q) { 85 int i = 0; 86 QNodePtr p; 87 p = Q.front; 88 while (Q.rear != p) { 89 i++; 90 cout << p->next->data << endl; 91 p = p->next; 92 } 93 } 94 95 // 若队列不空，则用e返回Q的队头元素，并返回1，否则返回-1 96 int Q_GetHead(LinkQueue Q, int &e) { 97 QNodePtr p; 98 if (Q.front == Q.rear) 99 return -1;100 p = Q.front->next;101 e = p->data;102 return 1;103 }104 105 // 插入元素e为Q的新的队尾元素106 void Q_Put(LinkQueue *Q, int e) {107 QNodePtr p = (QNodePtr)malloc(sizeof(QNode));108 if (!p) // 存储分配失败109 exit(OVERFLOW);110 p->data = e;111 p->next = NULL;112 //FIFO，将新节点追加到尾节点后面113 Q->rear->next = p;114 //将新的节点变成尾节点115 Q->rear = p;116 }117 118 119 // 若队列不空，删除Q的队头元素，用e返回其值，并返回1，否则返回-1120 int Q_Poll(LinkQueue *Q,int &e) {121 QNodePtr p;122 if (Q->front == Q->rear)123 return -1;124 //取出头节点125 p = Q->front->next;126 //取出头节点的数据127 e = p->data;128 cout << e << endl;129 Q->front->next = p->next;130 if (Q->rear == p)131 Q->rear = Q->front;132 free(p);133 cout << e << endl;134 return 1;135 }