当前位置： 首页 > article >正文

【数据结构初阶】——栈和队列

article 2024/12/24 11:42:10

【数据结构初阶】——栈和队列

文章目录

  • 【数据结构初阶】——栈和队列
    • 前言
    • 1. 栈
      • 1.1 栈的基本概念
      • 1.2 栈的常见基本操作
      • 1.3 栈的基本实现
    • 2. 队列
      • 2.1 队列的基本概念
      • 2.2 队列的常见基本操作
      • 2.3 队列的基本实现
    • 结语

前言

小伙伴们，大家好呀，今天我们学习的是数据结构中的栈和队列

之前我们写过【栈和队列的OJ题】，但是有很多小伙伴不知道栈和队列讲的是什么，咱们就好好聊聊

1. 栈

1.1 栈的基本概念

栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出 LIFO（Last In First Out） 的原则

在这里插入图片描述

栈顶：线性表允许进行插入删除的那一端

栈底：固定的，不允许进行插入和删除的另一端

空栈：不含任何元素的空表

值得注意的是，栈是一种遵循后进先出的结构。类似我们生活中的弹夹，羽毛球桶等等

在这里插入图片描述

1.2 栈的常见基本操作

  • STInit(ST* pst)：初始化一个空栈S

  • STEmpty(ST* pst)：判断一个栈是否为空，若栈为空则返回true，否则返回false

  • STPush(ST* pst, STDataType x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶

  • STPop(ST* pst)：出栈（栈的删除操作），若栈S非空，则移除栈顶元素

  • STTop(ST* pst)：读栈顶元素，若栈S非空，则返回栈顶元素

  • STDestroy(ST* pst)：栈销毁，并释放S占用的存储空间

  • STSize(ST* pst)：读取栈里元素个数，若栈S非空，则返回栈的元素个数

1.3 栈的基本实现

栈的定义

我们可以先定义一个栈的结构体，里面存放栈数组的指针， top 是栈顶元素的下标， capacity 是栈数组现在的空间大小

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

栈的初始化

top的初始化有两种方式：

  • top 可以 初始化为 -1

如果栈为空的情况出现，可以很明显地看出来，因为它是一个负数嘛，而且当 top = 0 时，我们也可以知道栈中有一个元素

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
    pst->top = -1;//指向栈的当前元素
}
  • top 可以 初始化为 0

这样初始化，top 就代表了栈的当前元素的下一个元素

但需要注意的是，如果栈为空，top = 0

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = pst->top = 0;//指向栈的当前元素的下一个元素
}

在这里插入图片描述

我们下面的操作，都是建立在 top 初始化为 0 的前提下，如果 top 初始化为 -1，有些操作可能会和我的有点出入哈

栈的销毁

栈的销毁很简单吧，我们先free销毁数组，然后再给数组指针指向空，再将 top 和 capacity 都给0表示栈为空

如果 top 初始化为 -1，这里就要给 -1 表示空

void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}

入栈

入栈之前我们需要先对栈进行判满，如果满了的话我们就需要扩容，扩容到原来的2倍

如果没开空间就先开4个空间。当我们没开空间时，a是空指针，此时realloc相当与malloc更好，然后再更新a和capacity，赋值x，top++

在这里插入图片描述

void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->capacity == pst->top)//栈满了
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;//未开空间就给4个空间，否则就在原来的空间扩容两倍
		STDataType* tmp = (STDataType*)realloc(pst->a,sizeof(STDataType)*newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail~");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top++] = x;//赋值 top++
}

出栈

出栈的时候，我们只需要控制top，想一想是不是 top-- 就可以了，至于top指向的值去哪了我就不关心了

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

获取栈顶元素

因为我们top是指向栈顶元素的下一个，所以我们就要返回下标为 top-1 的元素

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top-1];
}

判空

当 top = 0 时，栈为空

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

栈的元素个数

因为我们的 top 初始化为 0，是指向栈顶元素的下一个，就相当于栈的元素个数size，所以我们直接返回top即可

int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

栈的遍历

栈在遍历的时候先获取栈顶元素，然后在出栈，直到栈为空

int main()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	STDestroy(&s);
	return 0;
}

我们也可以一边进栈一边出栈，像这样

int main()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	printf("%d ", STTop(&s));
	STPop(&s);
	STPush(&s, 3);
	STPush(&s, 4);
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	STDestroy(&s);
	return 0;
}

大家可以自己试试

2. 队列

2.1 队列的基本概念

队列（Queue）：是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头

在这里插入图片描述

队头：允许删除的一端，又称队首

队尾：允许插入的一端

空队列：不包含任何元素的空表

值得注意的是，队列是一种遵循先进先出的结构。类似我们生活中的取号器，队列还可以进行好友推荐，也就是广度优先遍历（DFS），大家一下了解就可以了

2.2 队列的常见基本操作

  • QueueInit(Queue* pq)：初始化队列，构造一个空队列pq
  • QueueEmpty(Queue* pq)：判队列空，若队列Q为空返回true，否则返回false
  • QueuePush(Queue* pq, QDataType x)：入队，若队列Q未满，将x加入，使之成为新的队尾
  • QueuePop(Queue* pq)：出队，若队列Q非空，删除队头元素
  • QueueFront(Queue* pq)：读队头元素，若队列Q非空，则读取队头元素
  • QueueBack(Queue* pq)：读队尾元素，若队列Q非空，则读取队尾元素
  • QueueSize(Queue* pq)：读取队列里元素个数，若栈S非空，则返回栈的元素个数

2.3 队列的基本实现

队列结构体

我们需要先定义一个队列节点的结构体，然后在用一个头指针，一个尾指针，和一个size维护整个队列

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

为什么要建队列节点的结构体？

我们会发现如果不这样做，入队和出队会非常麻烦，这边我们还要传二级指针，因为我们要改变头指针，尾指针。大家想一想，我们要删指针，删完了要不是要改变外面的实参？插入的时候，要改变外面的实参，那就要把实参传递给形参的指针，这个指针的改变不会影响实参，是不是要传实参的地址，是不是很麻烦啊

// 队尾插入
void QueuePush(QNode** pphead, QNode** pptail, QDataType x);
// 队头删除
void QueuePop(QNode** pphead, QNode** pptail);

队列的初始化

我们就把头指针和尾指针都初始化为空，size初始化为0

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

队列的销毁

我们创建一个cur指针指向头节点，然后遍历销毁即可

注意要先保存下一个节点在销毁当前节点，然后移动cur即可，最后让头指针尾指针指向空，size为0即可

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	};
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

入队

我们需要malloc一个节点，因为是尾插，所以让节点指向空，赋值为x，如果没有节点，那头节点和尾节点都是指向新节点，否则尾插在尾节点后，新节点成为新的尾节点，最后size++

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* node = (QNode*)malloc(sizeof(QNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return;
	}
	node->next = NULL;
	node->val = x;
	if (pq->phead == NULL)//没有节点
	{
		pq->phead = pq->ptail = node;
	}
	else//至少有一个节点
	{
		pq->ptail->next = node;
		pq->ptail = node;
	}
	pq->size++;
}

获取队头元素

我们需要判一下队列是否为空，然后返回队头节点元素的值

QDataType QueueFron(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);
	return pq->phead->val;
}

获取队尾元素

我们需要判断一下队列是否为空，然后返回队尾节点元素的值

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);
	return pq->ptail->val;
}

出队

出队的时候要分两种情况

  • 第一，当队列中只有一个节点时，队头指针和队尾指针都要指向空，size–-
  • 第二，当队列中不只有一个节点时，我们就需要保存队头节点的下一个节点，释放头节点，保存的节点成为新的头节点，size–-
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);
	if (pq->phead == pq->ptail)//只有一个节点
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
		pq->size--;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
		pq->size--;
	}
}

队列的判空

判断size是否为0即可

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

队列的遍历

队列的遍历就是获取队头元素，然后删除队头元素直到队列为空

int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (q.size)
	{
		printf("%d ", QueueFron(&q));
		QueuePop(&q);
	}
	QueueDestroy(&q);
	return 0;
}

我们也可以一边入队一边出队，像这样

int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	printf("%d ", QueueFron(&q));
	QueuePop(&q);
	printf("%d ", QueueFron(&q));
	QueuePop(&q);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (q.size)
	{
		printf("%d ", QueueFron(&q));
		QueuePop(&q);
	}
	QueueDestroy(&q);
	return 0;
}

大家也可以试试

结语

这些就是栈和队列(初阶)的全部内容了，要是想做一点题的可以看看这篇哦【栈和队列OJ题】

感谢你能看到这里，希望这篇文章对你有用，溜了溜了，我们下篇再见吧


http://www.kler.cn/a/288995.html

相关文章：

  • 北京中小学信息学编程能力测评 BCSP-X 2024 下半年 真题汇总
  • ChatGPT之父：奥尔特曼
  • 【spring-cloud-gateway总结】
  • 使用C语言编写UDP循环接收并打印消息的程序
  • gitee给DeployKey添加push权限
  • Intel-ECI之Codesys PLC + Ethercat 远端IO + Codesys IDE编程
  • 求三元组中可能出现的最小距离
  • RabbitMQ练习（Routing）
  • 使用COAP和MQTT协议的多协议方法开发的用于机器人手术的自动医疗物联网系统
  • vue3+ts 实现模板表格文件下载~
  • pikachu文件包含漏洞靶场攻略
  • 密钥分发与公钥认证：保障网络通信的安全
  • MySQL入门学习-MySQL的连接查询
  • MySQL——事务与存储过程（二）存储过程的创建（4）光标的使用
  • 【Linux学习笔记】protobuf相关操作
  • 数仓基础（九）：各大公司实时数仓实践
  • Go锁 详解
  • k8s-使用Network Policies实现网络隔离
  • (二)、软硬件全开源智能手表，可全面高精度采集生命体征数据，进行健康检测。(HealthyPi Move)
  • 【Java中的三元运算符】
  • 书法图片自动扣字的批处理
  • leecode 31.下一个排列（Golang）
  • 深度学习100问27:什么是截断的BPTT
  • mysql的组从复制
  • 检测文件解析漏洞的工具
  • 技术Leader在训练团队思考力中的核心职责