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

数据结构与算法——栈和队列<也不过如此>

在这里插入图片描述

🏆作者主页:king&南星
🎄专栏链接:数据结构

在这里插入图片描述

🏅文章目录

    • 一、🥇栈
      • 1、🥈概念理解
      • 2、🥈链表头插头删实现栈
        • 1、🥉预备准备
        • 2、🥉创建结点函数
        • 3、🥉遍历函数
        • 4、🥉头插
        • 5、🥉头删
      • 3、🥈链表尾插尾删实现栈
    • 二、🥇队列
      • 1、🥈概念理解
      • 2、🥈数组头插尾删实现队列
        • 1、🥉预备准备
        • 2、🥉初始化
        • 3、🥉头插函数
        • 4、🥉浏览数据
        • 5、🥉删除数据
      • 3、🥈数组尾插头删实现队列

一、🥇栈

在讲解之前我先和大家说说栈有哪些好玩应用:比方说水桶,还有我们常用的撤销,粘贴板,大家学完这个可以用栈简单的实现一下四则运算😀

1、🥈概念理解

1、定义:栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
2、核心:
栈:先入后出,后入先出 First In Last Out FILO
先存进去的,最后才能拿出来
最后存进去的,一开始就能拿出来
3、图解:在这里插入图片描述

2、🥈链表头插头删实现栈

1、🥉预备准备

先把头文件和函数声明写好

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef struct Node
{
	int data;
	struct Node* next;
}Node;

#define SIZE sizeof(Node)

//创建新节点
Node* createNode(int newData);
//浏览
void watchData(Node* head);
//头插
void push_front(Node** head, int insertData);
//头删
void pop_front(Node** head);

2、🥉创建结点函数

注意:要判断空间是否申请成功

Node* createNode(int newData)
{
	//1 申请内存
	Node* newNode = (Node*)malloc(SIZE);
	assert(newNode);
	//2 数据赋值
	newNode->data = newData;
	newNode->next = NULL;
	//3 返回
	return newNode;
}

3、🥉遍历函数

void watchData(Node* head)
{
	printf("List:");
	while (head)
	{
		printf("%d ", head->data);
		//切换到下一个节点
		head = head->next;
	}
	printf("\n");
}

4、🥉头插

注意:
1.防止传入的是空结点
2.要传入二级指针,因为要改变头结点

void push_front(Node** head, int insertData)
{
	//1 防呆
	if (NULL == head) return;
	Node* pNode = createNode(insertData);
	//2 新节点的next指针指向原来的第一个结点
	pNode->next = *head;
	//3 新节点成为第一个节点
	*head = pNode;
}

5、🥉头删

要注意释放删除的结点和临时指针最后的指向

void pop_front(Node** head)
{
	if (NULL == head || NULL == *head) return;

	Node* pNode = *head;
	//第二个节点成为头结点
	*head = pNode->next;
	//释放头结点
	free(pNode);
	pNode = NULL;
	return;
}

3、🥈链表尾插尾删实现栈

一样的思路,这里我就不和大家啰嗦了,大家主要要记住栈的特点:先进后出,后进先出就可以了,代码我放下面了,感兴趣的可以看看哦!!!

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef struct Node
{
	int data;
	struct Node* next;
}Node;

#define SIZE sizeof(Node)

//创建新节点
Node* createNode(int newData);
//浏览
void watchData(Node* head);
//尾插
void push_back(Node** head, int insertData);
//尾删
void pop_back(Node** head);

int main()
{
	Node* List = NULL;  //创建链表
	push_back(&List, 999);
	watchData(List);
	push_back(&List, 888);
	watchData(List);
	pop_back(&List);
	watchData(List);
	for (int i = 0; i < 10; i++)
	{
		push_back(&List, i);
	}
	watchData(List);
	pop_back(&List);
	watchData(List);
	pop_back(&List);
	watchData(List);
	pop_back(&List);
	watchData(List);
	pop_back(&List);
	watchData(List);
	pop_back(&List);
	watchData(List);
	return 0;
}

Node* createNode(int newData)
{
	//1 申请内存
	Node* newNode = (Node*)malloc(SIZE);
	assert(newNode);
	//2 数据赋值
	newNode->data = newData;
	newNode->next = NULL;
	//3 返回
	return newNode;
}

void watchData(Node* head)
{
	printf("List:");
	while (head)
	{
		printf("%d ", head->data);
		//切换到下一个节点
		head = head->next;
	}
	printf("\n");
}

void push_back(Node** head, int insertData)
{
	//1 防呆
	if (NULL == head) return;
	Node* pNode = *head;
	Node* newNode = createNode(insertData);
	if (*head)//*head为真,非空链表
	{
		//找到最后一个
		while (pNode->next) pNode = pNode->next;
		pNode->next = newNode;
	}
	else //空链表
	{
		*head = newNode;
	}
}

void pop_back(Node** head)
{
	if (NULL == head) return;
	
	Node* pNode = *head;
	Node* pLiftNode = *head;
	if ( NULL == pNode->next )      //只有一个节点
	{
		//第二个成为新的头结点
		(*head) = (*head)->next;
		//释放节点
		free(pNode);
		pNode = NULL;
		return;
	}
	//找到最后一个和倒数第二个节点
	while (1)
	{
		pNode = pNode->next;
		if (NULL == pNode->next) break;
		pLiftNode = pNode;
	}
	//倒数第二个节点指向空
	pLiftNode->next = pNode->next;
	free(pNode);
	pLiftNode = pNode = NULL;
}

二、🥇队列

1、🥈概念理解

1、定义:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头
2、核心:
队列:先入先出,后入后出 First In First Out FIFO
做核酸 排队
食堂打饭 排队
看电影 排队
3、图解:在这里插入图片描述

2、🥈数组头插尾删实现队列

1、🥉预备准备

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef struct student
{
	char name[20];
	int age;
	double score;
}stu;
int curSize;        //记录当前元素个数
int capacity;       //记录当前容量
stu* pArr;          //指向当前内存段的首地址

//初始化
void initData();
//insertData
void push(stu* inserData);
//浏览数据
void watchData();
//删除数据
void pop(stu* delData);

2、🥉初始化

把当前元素个数和当前容量都赋值为0,把结构体指针爷指向空

//初始化
void initData()
{
	curSize = 0;
	capacity = 0;
	pArr = NULL;
}

3、🥉头插函数

这里用了很多的高端写法(比较刁钻),大家要看明白函数要熟悉位操作和内存函数的应用
1、右移一位就相当于除以2
2、memcpy内存复制函数,第一个参数是目的地,第二个参数是要复制的地方,第三个参数是大小
3、memmove内存移动函数,第一个参数是目的地,第二个参数是要移动的地方,第三参数是大小
==注意:==如果大家还没有明白,可以参照该🚩文章

void push(stu* inserData)
{
	//需要开内存
	if (capacity <= curSize)
	{
		//计算新开内存
		capacity += (capacity >> 1 > 1) ? (capacity >> 1) : 1;
		stu* pNew = (stu*)malloc(sizeof(stu) * capacity);//新开内存
		assert(pNew);     //防御性编程
		if (pArr)
		{
			memcpy(pNew+1, pArr , sizeof(stu) * curSize);
			//释放原有内存段
			free(pArr);
		}
		//pArr指向新开内存段
		pArr = pNew;
	}
	else
	{
		memmove(pArr + 1, pArr, sizeof(stu) * curSize);
	}
	//inserData放入数组中
#if 0
	memcpy(pArr, inserData, sizeof(stu));//pArr缓冲区溢出
#else	
	strcpy(pArr[0].name, inserData->name);
	pArr[0].age = inserData->age;
	pArr[0].score = inserData->score;
#endif
	//元素个数加一
	curSize++;
}

4、🥉浏览数据

这里写了一点不一样的东西:可以打印出容量和当前数据个数,可以看出空间使用情况🧠

void watchData()
{
	printf("pArr[%d][%d]:\n", curSize, capacity);
	for (int i = 0; i < curSize; i++)
	{
		printf("%s-%d-%.2f\n",
			pArr[i].name, pArr[i].age, (pArr + i)->score);
	}
	printf("\n");
}

5、🥉删除数据

这里是直接申请一个新的数组,直接拷贝过去

void pop(stu* delData)
{
	if (curSize < 1) return;
	if ( 1 == curSize )    //只有一个元素时
	{
		free(pArr);
		initData();
		return;
	}
	else
	{
		//申请新空间
		stu* pNew = (stu*)malloc(sizeof(stu) * (curSize - 1));
		assert(pNew);
		//拷贝,第一个到倒数第二个
		memcpy(pNew, pArr, sizeof(stu) * (curSize - 1));
		free(pArr);										//释放原来的空间
		pArr = pNew;									//pArr指向新数据
		curSize--;
		capacity = curSize;
		return;
	}
}

3、🥈数组尾插头删实现队列

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef struct student
{
	char name[20];
	int age;
	double score;
}stu;
int curSize;        //记录当前元素个数
int capacity;       //记录当前容量
stu* pArr;          //指向当前内存段的首地址

//初始化
void initData();
//insertData
void push(stu* inserData);
//浏览数据
void watchData();
//删除数据
void pop(stu* delData);

int main()
{
	initData();
	stu d[5] =
	{
		{ "关羽", 18, 18.67 },
		{ "张飞", 28, 28.67 },
		{ "赵云", 38, 38.67 },
		{ "马超", 48, 58.67 },
		{ "黄忠", 58, 48.67 }
	};
	for (int i = 0; i < 5; i++)
	{
		push(d + i);
	}
	watchData();
	pop(d);
	watchData();
	pop(d);
	watchData();
	pop(d);
	watchData();
	pop(d);
	watchData();
	return 0;
}

//初始化
void initData()
{
	curSize = 0;
	capacity = 0;
	pArr = NULL;
}

//insertData
void push(stu* inserData)
{
	//需要开内存
	if (capacity <= curSize)
	{
		//计算新开内存
		capacity += (capacity >> 1 > 1) ? (capacity >> 1) : 1;
		stu* pNew = (stu*)malloc(sizeof(stu) * capacity);//新开内存
		assert(pNew);     //防御性编程
		if (pArr)
		{
			memcpy(pNew, pArr, sizeof(stu) * curSize);
			//释放原有内存段
			free(pArr);
		}
		//pArr指向新开内存段
		pArr = pNew;
	}
	//inserData放入数组中
	memcpy(pArr + curSize, inserData, sizeof(stu));
	//元素个数加一
	curSize++;
}

//浏览数据
void watchData()
{
	printf("pArr[%d][%d]:\n", curSize, capacity);
	for (int i = 0; i < curSize; i++)
	{
		printf("%s-%d-%.2f\n",
			pArr[i].name, pArr[i].age, (pArr + i)->score);
	}
	printf("\n");
}

//删除数据
void pop(stu* delData)
{
	if (curSize < 1) return;
	if (curSize == 1)    //只有一个元素时
	{
		free(pArr);
		initData();
		return;
	}
	else
	{
		//申请新空间
		stu* pNew = (stu*)malloc(sizeof(stu) * (curSize - 1));
		assert(pNew);
		//拷贝,第二个到最后一个
		memcpy(pNew, pArr + 1, sizeof(stu) * (curSize - 1));
		free(pArr);       //释放原来的空间
		pArr = pNew;      //pArr指向新数据
		curSize--;
		capacity = curSize;
		return;
	}
}

🎉欢迎各位→点赞👏 + 收藏💞 + 留言🔔​
💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🐾


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

相关文章:

  • 《拉依达的嵌入式\驱动面试宝典》—计算机网络篇(二)
  • 腾讯云AI代码助手编程挑战赛——贪吃蛇小游戏
  • Swift Protocols(协议)、Extensions(扩展)、Error Handling(错误处理)、Generics(泛型)
  • STM32和国民技术(N32)单片机串口中断接收数据及数据解析
  • Windows下安装最新版的OpenSSL,并解决OpenSSL不是当前版本的问题,或者安装不正确的问题
  • C语言#define定义宏
  • 考虑充电负荷空间可调度特性的分布式电源与电动汽车充电站联合配置方法(Matlab代码实现)
  • 为什么需要在差分或者重要信号换层时在它们旁边加上地孔呢?
  • 什么是计数排序?
  • IP地址的分类
  • ASEMI代理瑞萨TW8825-LA1-CR汽车芯片
  • C++ 98/03 应该学习哪些知识4
  • 2023年中国高校计算机大赛-团队程序设计天梯赛(GPLT)上海理工大学校内选拔赛(同步赛)(H题)(线段树)
  • 国产航顺HK32F030M:定时器计数/PWM输出/输出翻转/输入捕获
  • 【操作系统复习】ch3 内存基础
  • 为什么VMware会给我多创建了两个网络呢?Windows和Linux为什么可以彼此ping的通呢
  • 【文心一言】什么是文心一言,如何获得内测和使用方法。
  • 基于python的奥运会历史数据分析【120年】
  • 「Python 基础」异步 I/O 编程
  • 数据分析之Matplotilb数据可视化
  • Integer和int的比较大小
  • HelloWorld
  • python并发编程多线程
  • QT VTK开发 (一、下载编译)
  • wait 和 notify
  • Cadence Allegro 导出Netin(back anno.)报告详解