队列的概念及结构：
队列是只允许一端进行插入数据操作，在另一端进行删除数据操作的滕树线性表，队列具有先进先出、后进后出的原则。
入队列时进行插入操作的一端被称为队尾，出队列时进行删除操作的一段被称为队头。
队列的实现：
队列和栈一样也可以用数组和链表的结构实现，但是队列使用链表的结构实现会更优一些，因为使用数组结构的话，出队列在数组头上出数据，每出一个数据就要遍历一次数组，效率会很低。如果反过来数组头上入数据，那每入一次数据就会遍历一次数组，所以链表的效果更优。
链表分为带头不带头、循环不循环、单向双向等共八种链表，我们选择哪种呢？首先带头不带头的影响不大，带头了无非就是多一个next的问题，实际上带头之后反而会有点鸡肋。队列实现不能选择循环链表，因为循环了，我们就不好找队尾了，入队操作的时候就会出现问题。最后没有双向的必要，因为我们没有找前一个节点的需求，反而要多写一个prev。所以使用于队列实现的最佳链表是单项不带头不循环链表。
代码实现：
#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int QDataType; typedef struct QListNode { struct QListNode* next; QDataType data; }QNode; //队列的结构 typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; //初始化队列 void QueueInit(Queue* q); //队尾入队列 void QueuePush(Queue* q, QDataType data); //队头出队列 void QueuePop(Queue* q); //获取队列头部元素 QDataType QueueFront(Queue* q); //获取队列队尾元素 QDataType QueueBack(Queue* q); //获取队列中有效元素个数 int QueueSize(Queue* q); //检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q); //销毁队列 void QueueDestroy(Queue* q);
#define _CRT_SECURE_NO_WARNINGS 1 #include "Queue.h" //队列初始化 void QueueInit(Queue* q) { q->head = NULL; q->tail = NULL; q->size = 0; } //入队列 void QueuePush(Queue* q, QDataType x) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (q->tail == NULL) { q->head = q->tail = newnode; } else { q->tail->next = newnode; q->tail = newnode; } q->size++; } //出队列 void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q)); if (q->head->next == NULL) { free(q->head); q->head = q->tail = NULL; q->size--; } else { QNode* del = q->head; q->head = q->head->next; q->size--; free(del); } } //获取队列头部元素 QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->head->data; } //获取队列队尾元素 QDataType QueueBack(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->tail->data; } //获取队列中有效元素的个数 int QueueSize(Queue* q) { assert(q); return q->size; } //检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q) { assert(q); return q->head == NULL && q->tail == NULL; } //销毁队列 void QueueDestroy(Queue* q) { assert(q); while (q->head) { QNode* next = q->head; q->head = q->head->next; free(next); } }
#define _CRT_SECURE_NO_WARNINGS 1 #include "Queue.h" void test() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); printf("%d\n", QueueFront(&q)); printf("%d\n", QueueBack(&q)); printf("%d\n", QueueSize(&q)); QueuePop(&q); QueuePop(&q); QueuePop(&q); printf("%d\n", QueueFront(&q)); printf("%d\n", QueueBack(&q)); printf("%d\n", QueueSize(&q)); QueueDestroy(&q); } int main() { test(); return 0; }
