C语言 之【队列的简介、队列的实现(初始化、烧毁、入队、出队、判空、元素个数、元素的访问)】

目次

1.队列的简介
2.队列的实现
2.1实现须知
2.2 头文件预览
2.2.1 头文件细节
2.3 队列的初始化
2.4 队列的烧毁
2.5 入队
2.6出队
2.7 判空
2.8 队列的元素个数
2.9队首元素与队尾元素
2.10 队列的打印

---

1.队列的简介

   队列是一种数据结构，也是一种特别的线性表
  队列只答应在一端举行插入数据操纵，在另一端举行删除数据操纵
  

    举行插入数据操纵的一端叫作队尾， 举行删除数据操纵的一端叫作队头
  队列服从先辈先出 FIFO(First In First Out)原则
  就像生存中顾客按到达顺序列队到超市收银员处结账一样，
  新顾客参加队尾，服务从队头开始，排在队头的顾客先结账离开
     插入数据操纵，简称入队；删除数据操纵，简称出队
  2.队列的实现

2.1实现须知

   前面说了，队列是是一种线性表，所以既可以用数组实现队列也可以用链表实现队列
  注意到：
  (1)数组、链表(给定尾指针的环境下)，尾插的服从均为O(1)，
  但链表只需按需申请空间，数组却要举行预分配空间，举行扩容操纵还可能造成空间浪费
  (2)数组、链表头删同样是 O(1)（数组不移动数据得环境下）
  所以队列的实现方式得基于详细场景，根据链表和数组的特性而定
  下面使用链表实现的队列
  

   (1)给定一个头指针head和一个尾指针tail就能实现尾插(入队)，头删(出队)
  所以，无头单向不循环链表就可实现队列
  2.2 头文件预览

1. #pragma once
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <stdbool.h>
5. #include <assert.h>
7. typedef int QueueDataType;
8. typedef struct QueueNode
9. {
10.         QueueDataType data;
11.         struct QueueNode* next;
12. }QNode;
13. //队列不仅需要实现单链表的头删，还要知晓元素个数，那么就是多个数据用结构体存储
14. typedef struct Queue
15. {
16.         QNode* head;
17.         QNode* tail;
18.         int size;
19. }Queue;
20. //初始化
21. void QueueInit(Queue* pq);
22. //销毁
23. void QueueDestroy(Queue* pq);
24. //入队
25. void QueuePush(Queue* pq, QueueDataType val);
26. //出队
27. void QueuePop(Queue* pq);
28. //判空
29. bool QueueEmpty(Queue* pq);
30. //大小
31. int QueueSize(Queue* pq);
32. //队首元素
33. QueueDataType QueueFront(Queue* pq);
34. //队尾元素
35. QueueDataType QueueBack(Queue* pq);

复制代码

2.2.1 头文件细节

   (1)防止头文件内容在同一个编译单元内被多次睁开

1. #pragma once

复制代码

(2)包罗须要的头文件(库函数、开空间、断言、布尔值)
    (3)数据范例重定名，(以后只改这一处，就可以改变栈所存储的数据范例)

1. typedef int QueueDataType;

复制代码

(4)为了轻便与区分度，将队列的节点定名为QNode，
    (5)在实现无头单向不循环链表时，只须要一个头指针head就可以完成一系列操纵
  但是如许会导致尾插服从低、无法直接获取队尾元素(服从均为O(N),因为须要找尾)
  实现队列时，我们再界说一个结构体Queue，存储
  变量head, 指向对头
  变量tail，指向队尾
  变量size，记录队列的元素个数
  如许之后，就无需在接口中设置多个参数，让用户传多个参数，
  到达用一个队列范例的指针管理队列全部节点的目的，也进步了尾插的服从
  2.3 队列的初始化

1. void QueueInit(Queue* pq)
2. {
3.         assert(pq);
5.         pq->head = pq->tail =  NULL;
6.         pq->size = 0;
8. }

复制代码

  (1)队列指针一定不为空，所以断言队列指针
  (1)空队列的状态就是 "空"
  2.4 队列的烧毁

1. void QueueDestroy(Queue* pq)
2. {
3.         assert(pq);
5.         QNode* cur = pq->head;
6.         while (cur)
7.         {
8.                 QNode* next = pq->head->next;
9.                 free(cur);
11.                 cur = next;
12.         }
14.         pq->head = pq->tail = NULL;
15.         pq->size = 0;
16. }

复制代码

  (1)队列指针一定不为空，所以断言队列指针
  (1)队列中，须要主动开释的空间就是节点所占据的空间
  遍历队列，逐个开释，并还原成空队列状态即可
  2.5 入队

1. void QueuePush(Queue* pq, QueueDataType val)
2. {
3.         assert(pq);
5.         QNode* newnode = (QNode*)malloc(sizeof(QNode));
6.         if (newnode == NULL)
7.         {
8.                 perror("malloc fail");
9.                 exit(1);
10.         }
11.         newnode->data = val;
12.         newnode->next = NULL;
13.         //尾插注意判空
14.         if (pq->head == NULL)
15.         {
16.                 assert(pq->tail == NULL);
18.                 pq->head = pq->tail = newnode;
19.         }
20.         else
21.         {
22.                 pq->tail->next = newnode;
23.                 pq->tail = newnode;
24.         }
26.         ++(pq->size);
27. }

复制代码

   (1)队列指针一定不为空，所以断言队列指针
  (2)用户只传入数据，函数体内部须要创建新节点存储数据
  (2)入队就是尾插，分两种环境举行尾插
  1.队列为空时，head、tail都要指向新节点
  2.不为空时，先将新节点链接到链表中，再改变节点的位置
  (3)++size
  2.6出队

1. void QueuePop(Queue* pq)
2. {
3.         assert(pq);
4.         assert(!QueueEmpty(pq));
6.         QNode* next = pq->head->next;
7.         free(pq->head);
8.         pq->head = next;
9.         //注意一个节点时的出队
10.         if (pq->head == NULL)
11.         {
12.                 pq->tail = NULL;
13.         }
14.         --(pq->size);
15. }

复制代码

   (1)队列指针一定不为空，所以断言队列指针
   (1)出队时，队列一定不为空，所以断言队列
  (1) 出队就是头删，但是须要注意只有一个节点时的头删
  此时须要改变尾指针的指向
  

  (3)--size
  2.7 判空

1. bool QueueEmpty(Queue* pq)
2. {
3.         assert(pq);
5.         return pq->size == 0;
6. }

复制代码

    (1)队列指针一定不为空，所以断言队列指针
  （2）直接判断size即可
  2.8 队列的元素个数

1. int QueueSize(Queue* pq)
2. {
3.         assert(pq);
5.         return pq->size;
6. }

复制代码

   
    (1)队列指针一定不为空，所以断言队列指针
  （2）直接返回size即可
  2.9队首元素与队尾元素

1. //队首元素
2. QueueDataType QueueFront(Queue* pq)
3. {
4.         assert(pq);
5.         assert(!QueueEmpty(pq));
7.         return pq->head->data;
8. }
9. //队尾元素
10. QueueDataType QueueBack(Queue* pq)
11. {
12.         assert(pq);
13.         assert(!QueueEmpty(pq));
15.         return pq->tail->data;
16. }

复制代码

   (1)队列指针一定不为空，所以断言队列指针
   (1)访问元素时，队列一定不为空(队列为空时访问是无效操纵)，所以断言队列
   (1)直接返回对应节点存储的数据
  2.10 队列的打印

   队列并不支持遍历访问，只支持访问队头元素和队尾元素，即不提供遍历访问的接口
  想要知道全部元素
  只能边访问队头元素，边出队
  当然，如果须要保存元素，可提宿世存一下

1.         Queue pq;
2.         QueueInit(&pq);
3.         QueuePush(&pq, 1);
4.         QueuePush(&pq, 2);
5.         QueuePush(&pq, 3);
6.         QueuePush(&pq, 4);
7.         QueuePush(&pq, 5);
8.         QueuePush(&pq, 6);
9.        
10.     while (!QueueEmpty(&pq))
11.         {
12.                 printf("%d ", QueueFront(&pq));
13.                 QueuePop(&pq);
14.         }

复制代码