队列
一、队列的概念
队列只允许在一端进行数据的插入,在另一端进行数据的删除,插入数据的一端叫队尾,删除数据的一端叫队头。
实现队列时可以选择数组或者链表,如果选择数组实现,那么在删除数据时会造成数据的挪动,效率低下,因此这里选择使用链表实现队列。
二、队列的实现
使用链表实现队列,入队操作对应于链表的尾插,出队操作对应于链表的头删。一端插入数据,一端删除数据。假如只使用一个头指针指向队头,那么每次插入数据时都需要遍历链表找到尾结点,效率低下,因此选择增加一个尾指针,指向尾结点。
因此队列设计这样的两个结构体
typedef int QDataType;//便于对数据类型进行修改
//队列结点的结构体
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size; //队列大小
}Queue;
这样做可以减少函数的参数。
三、常用接口
队列的一些常用接口包括初始化队列、销毁队列、入队、出队、获取队头数据、获取队尾数据、获取队列的大小等
1、初始化和销毁
最开始,队列一个结点都没有,那么头尾指针都为NULL,队列大小为0。
销毁时,遍历队列依次释放每个结点即可。
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
2、入队
入队操作对应的是链表的尾插操作。插入时,需要注意队列结点数是否为0;
结点数为0:这时插入结点后,它是头结点,也是尾结点,头尾指针都应该指向它
结点数不为0:这时只需要改变尾指针,使它指向的结点指向新结点,在将自己指向新节点即可。
//队尾入队
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//创建新节点
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
return;
}
newNode->val = x;
newNode->next = NULL;
//队列为空
if (pq->head == NULL)
{
pq->head = pq->tail = newNode;
}
//队列不为空
else
{
pq->tail->next = newNode;
pq->tail = newNode;
}
pq->size++;
}
3、出队
出队操作对应于链表的头删。同样分为两种情况,队列只有一个结点和多于一个结点。一个结点时,删除后,队列为空,此时需要修改头尾两个指针。多于一个结点时,就是链表的头删了,链表的头删相信大家都掌握了,这里就不在过多赘述。
//队头出队
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq)); //队列不能为空
//只有一个结点
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* cur = pq->head->next; //存储第二个结点的地址
free(pq->head);
pq->head = cur;
}
pq->size--;
}
4、获取队头和队尾的元素
由于我们结构体的设计,有指向队列头尾结点的指针,那么这两个接口就变得容易实现了。
//队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->val;
}
//队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->val;
}
5、判空和获取队列大小
判空:由于只在队头处出数据,因此只需要判断head指针是否为空,就可以知道队列是否为空;也可以使用size是否为0来判断。
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
//return pq->head == NULL;
return pq->size == 0;
}
这两种写法都可以。
获取队列大小:size的大小就是队列的大小
//队列大小
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
四、队列的应用
队列这个数据结构有什么应用呢?在实现二叉树的层序遍历和判断二叉树是否为完全二叉树时,队列就可以做到。如何做到的,这里就先放代码,大家自己研究一下,后续会有关于树的介绍。
// 判断树是否是完全二叉树
bool TreeComplete(BTNode* root)
{
if (root == NULL)
{
return true;
}
//创建和初始化队列
Queue TreeQ;
QueueInit(&TreeQ);
//插入根节点
QueuePush(&TreeQ, root);
while (!QueueEmpty(&TreeQ))
{
//获得队头
BTNode* front = QueueFront(&TreeQ);
//遇到空跳出循环
if (!front)
{
break;
}
//将队头结点的左右孩子结点入队
QueuePush(&TreeQ, front->left);
QueuePush(&TreeQ, front->right);
//删除队头
QueuePop(&TreeQ);
}
while (!QueueEmpty(&TreeQ))
{
BTNode* front = QueueFront(&TreeQ);
//有非空说明不是完全二叉树
if (front)
{
QueueDestroy(&TreeQ);
return false;
}
QueuePop(&TreeQ);
}
QueueDestroy(&TreeQ);
return true;
}
// 层序遍历
void TreeLevelOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
//创建和初始化队列
Queue TreeQ;
QueueInit(&TreeQ);
//插入根节点
QueuePush(&TreeQ, root);
while (!QueueEmpty(&TreeQ))
{
//获得队头
BTNode* front= QueueFront(&TreeQ);
//将队头结点的左右孩子结点入队
if(front->left != NULL)
QueuePush(&TreeQ, front->left);
if (front->right != NULL)
QueuePush(&TreeQ, front->right);
//打印队头结点数值
printf("%c ", front->val);
//删除队头
QueuePop(&TreeQ);
}
}
这里存入队列的数据不是二叉树结点,而是二叉树结点的指针。
五、完整代码
queue.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq,QDataType x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
//队尾入队
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//创建新节点
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
return;
}
newNode->val = x;
newNode->next = NULL;
//队列为空
if (pq->head == NULL)
{
pq->head = pq->tail = newNode;
}
//队列不为空
else
{
pq->tail->next = newNode;
pq->tail = newNode;
}
pq->size++;
}
//队头出队
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq)); //队列不能为空
//只有一个结点
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* cur = pq->head->next; //保留第二个结点
free(pq->head);
pq->head = cur;
}
pq->size--;
}
//队列大小
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
//队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->val;
}
//队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->val;
}
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
//return pq->size == 0;
}
关于队列就介绍这些了,学会这么多数据结构后,需要多多的练手,保持手感,不要让自己手生,因此后面会带大家写一些题目。