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

【数据结构】栈和队列（笔记总结）

article 2024/11/13 6:48:19

在这里插入图片描述

👦个人主页：@Weraphael
✍🏻作者简介：目前学习C++和算法
✈️专栏：数据结构
🐋 希望大家多多支持，咱一起进步！😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨

【本章内容】

在这里插入图片描述

目录

  • 一、栈
      • 1.1 概念
      • 1.2 栈的结构
      • 1.3 准备工作
      • 1.4 常见接口
      • 1.5 代码实现之栈的初始化
      • 1.6 代码实现之栈的销毁
      • 1.7 代码实现之栈的尾插
      • 1.8 代码实现之栈的尾删
      • 1.9 代码实现之栈的大小
      • 1.9 代码实现之判断栈是否为空
      • 1.10 代码实现之返回栈顶元素
      • 1.11 test.c
  • 二、队列
      • 2.1 概念
      • 2.2 队列的结构
      • 2.3 准备工作
      • 1.4 常见接口
      • 1.5 队列之头尾指针初始化
      • 1.5 队列之内存空间的销毁
      • 1.6 队列之尾插
      • 1.7 队列之头删
      • 1.8 队列之求队列大小
      • 1.9 队列之判断队列是否为空
      • 1.10 队列之求队头元素
      • 1.11 队列之求队尾元素
      • 1.12 test.c部分

一、栈

1.1 概念

  • 栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作。其中进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的元素遵守后进先出LIFO(Last In First Out)的原则。
  • 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
  • 出栈：栈的删除操作叫做出栈，出数据也是在栈顶。
    在这里插入图片描述

1.2 栈的结构

栈的实现既可以使用顺序表实现，也可以用链表实现。但是，栈使用顺序表实现会比链表实现更有优势。因为栈是后进（栈顶进）的先出（栈顶出），实现一个栈需要尾插和尾删，而顺序表的尾插和尾删效率高，它的时间复杂度都是O(1)，而单链表的尾插和尾删比顺序表低，它的时间复杂度是O(n)
对于顺序表大家可以看看这边博客 —> 点击跳转

【结构】

typedef struct Stack
{
	int* a;  	//指向动态开辟的数组
	int top; 	//表示栈顶
	int capacity;//容量空间的大小
}Stack;

1.3 准备工作

为了方便管理，我们可以创建多个文件来实现
test.c - 测试代码逻辑 （源文件）
stack.c - 动态的实现 （源文件）
stack.h - 存放函数的声明 （头文件）
在这里插入图片描述

1.4 常见接口

【stack.h】

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

//栈的初始化
void STInit(Stack* ps);

//栈的销毁
void STDestroy(Stack* ps);

//栈的尾插
void STPush(Stack* ps, int x);

//栈的尾删
void STPop(Stack* ps);

//栈的大小
int STSize(Stack* ps);

//栈是否为空
bool STEmpty(Stack* ps);

//栈顶元素
int STTop(Stack* ps);

1.5 代码实现之栈的初始化

【stack.c】

//栈的初始化
void STInit(Stack* ps)
{
	assert(ps);
	ps->a = (int*)malloc(sizeof(int) * 4);
	if (ps->a == NULL)
	{
		perror("ps->a :: malloc");
		return;
	}
	ps->top = 0;
	ps->capacity = 4;
}
  • 详细细节参考这篇博客： 点击跳转

1.6 代码实现之栈的销毁

【stack.c】

//栈的销毁
void STDestroy(Stack* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;

	ps->capacity = 0;
	ps->top = 0;
}
  • 详细细节参考这篇博客： 点击跳转

1.7 代码实现之栈的尾插

【stack.c】

//栈的尾插
void STPush(Stack* ps, int x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->top == ps->capacity)
	{
		int* tmp = (int*)realloc(ps->a, sizeof(int) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("tmp :: realloc");
			return;
		}
		ps->capacity *= 2;
		ps->a = tmp;
		tmp = NULL;
	}
	//尾插
	ps->a[ps->top] = x;
	ps->top++;
}
  • 详细细节参考这篇博客： 点击跳转

1.8 代码实现之栈的尾删

【stack.c】

//栈的尾删
void STPop(Stack* ps)
{
	assert(ps);
	//特判顺序表为空的情况
	assert(!STEmpty(ps));

	ps->top--;
}
  • 详细细节参考这篇博客： 点击跳转

1.9 代码实现之栈的大小

【stack.c】

//栈的大小
int STSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}

【学习笔记】
一开始初始化栈顶top为 0，表示栈尾插后，top会指向栈顶的下一个元素。因此top就代表整个栈的大小。

1.9 代码实现之判断栈是否为空

【stack.c】

//栈是否为空
bool STEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

1.10 代码实现之返回栈顶元素

【stack.c】

//栈顶元素
int STTop(Stack* ps)
{
	assert(ps);
	//当ps->top 为 0时，会导致越界
	assert(ps->top != 0);//assert(!STEmpty(ps));
	
	return ps->a[ps->top - 1];
}

1.11 test.c

#include "stack.h"

int main()
{
	Stack st;
	STInit(&st);

	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	
	//注意：栈不能直接打印，因为它在途中出数据
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	STDestroy(&st);

	return 0;
}

二、队列

2.1 概念

  • 只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
  • 队列具有先进先出FIFO(First In First Out)
  • 入队列：进行插入操作的一端称为队尾
    出队列：进行删除操作的一端称为队头

在这里插入图片描述

2.2 队列的结构

首先队列也可以用顺序表和链表的结构实现，但是，使用链表实现会更优一些，为什么呢？

答：首先队列是先进先出的，并且它需要尾插和头删。所以，对于顺序表来说，尾删是比单链表快很多，但其头删却要移动整个数据，就显得非常麻烦。而对于单链表来说，头删是非常easy的，而尾插需要遍历，时间复杂度是O（n）

【结构】

typedef struct QNode
{
	struct QNode* next;
	int data;
}QNode;


typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

大家可能会有点奇怪，为什么在单链表章节不定义一个首尾指针结构体？
答案是：因为队列需要尾插而不需要尾删，什么意思呢？对于普通单链表来说，在尾删之前是需要记录尾节点的前一个节点的，即使在单链表上定义一个首尾指针结构体，但时候尾删还是得遍历一遍链表来找到尾节点的前一个结点，因此普通单链表再定义一个首尾指针结构体有点白费力气，而队列不同，它只进行头删和尾插的操作。

2.3 准备工作

为了方便管理，我们可以创建多个文件来实现
test.c - 测试代码逻辑 （源文件）
Queue.c - 动态的实现 （源文件）
Queue.h - 存放函数的声明 （头文件）
在这里插入图片描述

1.4 常见接口

【Queue.h】

typedef struct QNode
{
	struct QNode* next;
	int data;
}QNode;


typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size; // 队列大小
}Queue;

//头指针和尾指针的初始化
void QueueInit(Queue* pq);

//开辟内存空间的销毁
void QueueDestroy(Queue* pq);

//队列的尾插
void QueuePush(Queue* pq, int x);

//队列的头删
void QueuePop(Queue* pq);

//队列的大小
int QueueSize(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

//队头数据
int QueueFront(Queue* pq);

//队尾数据
int QueueBack(Queue* pq);

1.5 队列之头尾指针初始化

//头指针和尾指针的初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

【笔记总结】

  1. 断言问题。pq是一个结构体指针，指向一个首尾指针的结构体，pq指向NULL，这个队列就没法玩了
    在这里插入图片描述

1.5 队列之内存空间的销毁

//开辟内存空间的销毁
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;
}

1.6 队列之尾插

//队列的尾插
void QueuePush(Queue* pq, int x)
{
	assert(pq);
	//尾插的第一步，先向内存申请空间
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("newnode :: malloc");
		return;
	}
	//再对newnode初始化
	newnode->data = x;
	newnode->next = NULL;

	//接下来开始尾插
	//第一个问题：当前的链表可能为空
	if (pq->head == NULL)
	{
		//在链表为空的情况下tail，也一定为空（特判）
		//若tail不为空就是传错了
		assert(pq->tail == NULL);
		//直接赋值即可
		pq->head = pq->tail = newnode;
	}
	//否则就是正常的尾插
	else
	{
		//tail newnode
		pq->tail->next = newnode;
		pq->tail = newnode; //更新tail
	}
	//尾插后size个数+1
	pq->size++;
}

1.7 队列之头删

//队列的头删
void QueuePop(Queue* pq)
{
	assert(pq);
	//空链表是不能头删的
	assert(pq->head != NULL);
	
	//头删的特殊情况：链表中只有一个节点
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//接下来就是正常的头删
	else
	{
		//记录头节点的下一个节点
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	//删掉一个元素，队列的个数就要减1
	pq->size--;
}

1.8 队列之求队列大小

//队列的大小
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

1.9 队列之判断队列是否为空

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

1.10 队列之求队头元素

//队头数据
int QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

1.11 队列之求队尾元素

//队尾数据
int QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

1.12 test.c部分

#include "Queue.h"

int main()
{
	Queue node;
	QueueInit(&node);

	//入队列（尾插）
	QueuePush(&node, 1);
	QueuePush(&node, 2);
	QueuePush(&node, 3);
	QueuePush(&node, 4);

	//注意：队列不能直接打印，因为它在途中出数据
	while (!QueueEmpty(&node))
	{
		printf("%d ", QueueFront(&node));
		QueuePop(&node);
	}
	printf("\n");

	QueueDestroy(&node);
	return 0;
}

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

相关文章：

  • 【时间之外】IT人求职和创业应知【34】-人和机器人，机器人更可靠
  • 项目模块详细说明
  • centos查看硬盘资源使用情况命令大全
  • echarts-gl 3D柱状图配置
  • 解耦与模块化：鸿蒙平台上的服务注册与查找机制
  • 无人机反制技术与方法：主动防御，被动防御技术原理详解
  • PHP请求的好处，PHP如何请求淘宝开放接口
  • 代码随想录算法训练营第38天|509. 斐波那契数，70. 爬楼梯，746. 使用最小花费爬楼梯
  • 20230403在WIN10下通过ffmpeg调用NVIDIA的硬件加速wmv视频转码为MP4格式
  • WEB系统页面超过一定时间就自动跳转至登录页（或退出）
  • ios jenkins配置实现iOS项目自动化打包
  • 初谈 ChatGPT
  • 【python界面编程】基于tinker界面编程加法
  • 如何降低node 包版本
  • 一文读懂：低代码开发平台对企业效益有什么作用？
  • ant design pro + umi4的动态菜单与动态路由
  • 带你玩转Python爬虫（胆小者勿进）千万别做坏事·······
  • 明明有index.jsp文件访问的时候却显示404
  • 指针C语言基础代码总结
  • 图嵌入 Node2Vec
  • 前端开发必看100道大厂面试题集锦（一）
  • 网站怎么接入chatGPT来自动写文章
  • python【反爬、xpath解析器、代理ip】
  • ZooKeeper领导者选举流程
  • 子集和问题
  • 华为OD机试-通信误码-2022Q4 A卷-Py/Java/JS