赞
踩
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out)。
入队列:进行插入操作的一端称为队尾。
出队列:进行删除操作的一端称为队头。
- 入队,不需要移动任何元素,时间复杂度为 O(1) 。
- 出队,所有元素需要往前移动,时间复杂度为 O(N) 。
首先我们定义两个指针,队头指针指向第一个节点,队尾指针指向尾节点。
- 入队(尾插),时间复杂度为 O(1) 。
- 出队(头删),时间复杂度为 O(1) 。
如果使用数组删除队头数据,再挪动数据效率为 O(N),不适合。 选择用单向链表来完成队列的实现更好,可以发现头删和尾插效率都很高,而双向链表在这里发挥不出很大的作用。
- test.c(主函数、测试队列各个接口功能)
- Queue.c(队列接口函数的实现)
- Queue.h(队列的类型定义、接口函数声明、引用的头文件)
- // Queue.h
- // 链式结构:表示队列
- #pragma once
- #include<stdio.h>
- #include<stdbool.h> //bool
- #include<assert.h> // assert
- #include<stdlib.h> // malloc
-
- typedef int QDataType;
-
- typedef struct QueueNode // 队列节点结构
- {
- struct QueueNode* next; // 节点指针
- QDataType data; // 节点数据
- }QueueNode;
-
- typedef struct Queue // 队列的链式结构
- {
- QueueNode* head; //队头指针
- QueueNode* tail; //队尾指针
- }Queue;
-
- // 初始化队列
- void QueueInit(Queue* pq);
- // 销毁队列
- void QueueDestroy(Queue* pq);
- // 队尾入队列
- void QueuePush(Queue* pq, QDataType data);
- // 队头出队列
- void QueuePop(Queue* pq);
- // 获取队列头部元素
- QDataType QueueFront(Queue* pq);
- // 获取队列队尾元素
- QDataType QueueBack(Queue* pq);
- // 获取队列中有效元素个数
- int QueueSize(Queue* pq);
- // 检测队列是否为空,如果为空返回非零结果,如果非空返回0
- bool QueueEmpty(Queue* pq);
- // 初始化队列
- void QueueInit(Queue* pq)
- {
- assert(pq);
- pq->head = pq->tail = NULL;
- }
- // 销毁队列
- void QueueDestroy(Queue* pq)
- {
- assert(pq);
- QueueNode* cur = pq->head;
- while (cur)
- {
- QueueNode* next = cur->next;
- free(cur);
- cur = next;
- }
- cur = NULL;
- pq->head = pq->tail = NULL;
- }
- // 队尾入队列
- void QueuePush(Queue* pq, QDataType x)
- {
- assert(pq);
- QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); // 动态申请一个节点
- newnode->data = x;
- newnode->next = NULL; // 尾节点next指针置空
-
- if (pq->head == NULL) // 队列为空
- {
- pq->head = pq->tail = newnode;
- }
- else // 队列不为空
- {
- pq->tail->next = newnode;
- pq->tail = newnode; // 更新队尾指针
- }
- }
- // 队头出队列
- // 写法一:
- void QueuePop(Queue* pq)
- {
- assert(pq);
-
- //温柔处理方式:
- /* if(pq->head == NULL)
- return; */
-
- //暴力处理方式:
- assert(!QueueEmpty(pq));
-
- QueueNode* next = pq->head->next; // 记录头节点的直接后继
- free(pq->head); // 释放头节点
- pq->head = next; // 更新队头指针
- if (pq->head == NULL) // 队列中只有一个节点
- {
- pq->tail = NULL;
- }
- }
-
- // 写法二:
- void QueuePop(Queue* pq)
- {
- assert(pq);
-
- //暴力处理方式:
- assert(!QueueEmpty(pq));
-
- if(pq->head->next == NULL) // 一个节点
- {
- free(pq->head);
- pq->head = pq->tail = NULL;
- }
- else // 多个节点
- {
- QueueNode* next = pq->head->next; // 记录头节点的直接后继
- free(pq->head); // 释放头节点
- pq->head = next; // 更新队头指针
- }
- }
注意:链表只有一个节点时,要单独处理,否则可能会造成 pq->tail 野指针的情况。
- // 获取队列头部元素
- QDataType QueueFront(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
- return pq->head->data;
- }
- // 获取队列队尾元素
- QDataType QueueBack(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
- return pq->tail->data;
- }
- // 获取队列中有效元素个数
- int QueueSize(Queue* pq)
- {
- assert(pq);
- int n = 0;
- QueueNode* cur = pq->head;
- while (cur)
- {
- n++;
- cur = cur->next;
- }
- return n;
- }
如果频繁调用这个接口函数,可以在 QueuePtr 中加一个 size 来记录数据的个数。
- // 检测队列是否为空,如果为空返回非零结果,如果非空返回0
- bool QueueEmpty(Queue* pq);
- {
- assert(pq);
- return pq->head == NULL && pq->tail == NULL;
- }
- // Queue.c
- #include "Queue.h"
-
- // 初始化队列
- void QueueInit(Queue* pq)
- {
- assert(pq);
- pq->head = pq->tail = NULL;
- }
-
- // 销毁队列
- void QueueDestroy(Queue* pq)
- {
- assert(pq);
- QueueNode* cur = pq->head;
- while (cur)
- {
- QueueNode* next = cur->next;
- free(cur);
- cur = next;
- }
- cur = NULL;
- pq->head = pq->tail = NULL;
- }
-
- // 队尾入队列
- void QueuePush(Queue* pq, QDataType x)
- {
- assert(pq);
- QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); // 动态申请一个节点
- newnode->data = x;
- newnode->next = NULL; // 尾节点next指针置空
-
- if (pq->head == NULL) // 队列为空
- {
- pq->head = pq->tail = newnode;
- }
- else // 队列不为空
- {
- pq->tail->next = newnode;
- pq->tail = newnode; // 更新队尾指针
- }
- }
-
- // 队头出队列
- void QueuePop(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
-
- QueueNode* next = pq->head->next; // 记录头节点的直接后继
- free(pq->head); // 释放头节点
- pq->head = next; // 更新队头指针
- if (pq->head == NULL) // 队列中只有一个节点
- {
- pq->tail = NULL;
- }
- }
-
- // 获取队列头部元素
- QDataType QueueFront(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
- return pq->head->data;
- }
-
- // 获取队列队尾元素
- QDataType QueueBack(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
- return pq->tail->data;
- }
-
- // 获取队列中有效元素个数
- int QueueSize(Queue* pq)
- {
- assert(pq);
- int n = 0;
- QueueNode* cur = pq->head;
- while (cur)
- {
- n++;
- cur = cur->next;
- }
- return n;
- }
-
- // 检测队列是否为空,如果为空返回非零结果,如果非空返回0
- bool QueueEmpty(Queue* pq);
- {
- assert(pq);
- return pq->head == NULL && pq->tail == NULL;
- }
实际中我们有时还会使用一种队列叫循环队列。环形队列可以使用数组实现,也可以使用循环链表实现。
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。