顺序栈与链式栈

目录

1.  栈

1.1 栈的概念

2.  栈的实现

3. 顺序栈的实现

3.1 顺序栈的声明

3.2 顺序栈的初始化

3.3 顺序栈的入栈

 3.4 顺序栈的出栈

3.5 顺序栈获取栈顶元素

3.6 顺序栈获取栈内有效数据个数

3.7 顺序栈判断栈是否为空

3.8 顺序栈打印栈内元素

3.9 顺序栈销毁栈

3.10 完整代码

4. 链式栈的实现

4.1 链式栈的声明

4.2 链式栈的初始化

4.3 链式栈的入栈

4.4 链式栈的出栈

4.5 链式栈获取栈顶元素

4.6 链式栈获取栈内有效数据个数

4.7 链式栈判断栈是否为空

4.8 链式栈打印栈内元素

4.9 链式栈销毁栈

5. 疑问

1.  栈

1.1 栈的概念

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

压栈：栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

2.  栈的实现

我们了解了栈的概念，我们就可以发现，栈其实可以用顺序表和链表来实现，我们根据它的实现方式，可以把它分为顺序栈与链式栈。

3. 顺序栈的实现

Stack.h

//需要用到的库函数的头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* arr;//指向动态开辟的一块空间
	int top;//指向栈顶元素的下一个位置
	int capacity;//栈的容量
}st;

//初始化栈
void STInit(st* pst);
//入栈
void STPush(st* pst,STDataType x);
//出栈
void STPop(st* pst);
//获取栈顶元素
STDataType STTop(st* pst);
//获取栈内有效数据个数
int STSize(st* pst);
//判断栈是否为空
bool STEmpty(st* pst);
//打印栈内元素
void STPrint(st* pst);
//销毁栈
void STDestroy(st* pst);

3.1 顺序栈的声明

Stack.h

typedef int STDataType;

typedef struct Stack
{
	STDataType* arr;//指向动态开辟的一块空间
	int top;//指向栈顶元素的下一个位置
	int capacity;//栈的容量
}st;

这里我们在声明顺序栈的结构的时候，这个top可以是指向栈顶元素的，那我们在进行栈的初始化就需要将他初始化为-1，如果top是指向栈顶元素的下一个，那我们就需要将他的初始化设置为0。两种方法均可行，这里可以根据自己的习惯进行设置。

3.2 顺序栈的初始化

Stack.c

void STInit(st* pst)
{
	//判断pst是否为空指针
	assert(pst);
	pst->arr = NULL;
	pst->capacity = pst->top = 0;
}

3.3 顺序栈的入栈

Stack.c

void STPush(st* pst, STDataType x)
{
	//判断pst是否为空指针
	assert(pst);
	//检查空间大小，是否需要增容
	if (pst->capacity == pst->top)
	{
		int newcapacity = pst->capacity == 0 ? 4 :2 * pst->capacity;
		STDataType* tmp = (STDataType*)realloc(pst->arr,newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		pst->arr = tmp;
		pst->capacity = newcapacity;
	}
	//入数据
	pst->arr[pst->top++] = x;
}

 3.4 顺序栈的出栈

Stack.c

void STPop(st* pst)
{
	//判断pst是否为空指针
	assert(pst);
	//判断栈是否为空
	assert(pst->top > 0);

	pst->top--;
}

3.5 顺序栈获取栈顶元素

Stack.c

STDataType STTop(st* pst)
{
	//判断pst是否为空指针
	assert(pst);
	//判断栈是否为空
	assert(pst->top > 0);
	//这里top指向栈顶元素的下一个位置，-1刚好指向栈顶元素
	return pst->arr[pst->top - 1];
}

3.6 顺序栈获取栈内有效数据个数

Stack.c

int STSize(st* pst)
{
	assert(pst);

	return pst->top;
}

3.7 顺序栈判断栈是否为空

Stack.c

bool STEmpty(st* pst)
{
	assert(pst);

	return pst->top == 0;
}

3.8 顺序栈打印栈内元素

Stack.c

void STPrint(st* pst)
{
	assert(pst);
	while(!STEmpty(pst))
	{
		printf("%d\n", STTop(pst));
		STPop(pst);
	}
}

3.9 顺序栈销毁栈

Stack.c

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

3.10 完整代码

Stack.h

//需要用到的库函数的头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* arr;//指向动态开辟的一块空间
	int top;//指向栈顶元素的下一个位置
	int capacity;//栈的容量
}st;

//初始化栈
void STInit(st* pst);
//入栈
void STPush(st* pst,STDataType x);
//出栈
void STPop(st* pst);
//获取栈顶元素
STDataType STTop(st* pst);
//获取栈内有效数据个数
int STSize(st* pst);
//判断栈是否为空
bool STEmpty(st* pst);
//打印栈内元素
void STPrint(st* pst);
//销毁栈
void STDestroy(st* pst);

Stack.c

#include"Stack.h"

void STInit(st* pst)
{
	//判断pst是否为空指针
	assert(pst);
	pst->arr = NULL;
	pst->capacity = pst->top = 0;
}

void STPush(st* pst, STDataType x)
{
	//判断pst是否为空指针
	assert(pst);
	//检查空间大小，是否需要增容
	if (pst->capacity == pst->top)
	{
		int newcapacity = pst->capacity == 0 ? 4 :2 * pst->capacity;
		STDataType* tmp = (STDataType*)realloc(pst->arr,newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		pst->arr = tmp;
		pst->capacity = newcapacity;
	}
	//入数据
	pst->arr[pst->top++] = x;
}

void STPop(st* pst)
{
	//判断pst是否为空指针
	assert(pst);
	//判断栈是否为空
	assert(pst->top > 0);

	pst->top--;
}

STDataType STTop(st* pst)
{
	//判断pst是否为空指针
	assert(pst);
	//判断栈是否为空
	assert(pst->top > 0);
	//这里top指向栈顶元素的下一个位置，-1刚好指向栈顶元素
	return pst->arr[pst->top - 1];
}

int STSize(st* pst)
{
	assert(pst);

	return pst->top;
}

bool STEmpty(st* pst)
{
	assert(pst);

	return pst->top == 0;
}

void STPrint(st* pst)
{
	assert(pst);
	while(!STEmpty(pst))
	{
		printf("%d\n", STTop(pst));
		STPop(pst);
	}
}

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

4. 链式栈的实现

Stack.h

//需要用到的库函数的头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int STDataType;

typedef struct StackNode //定义节点结构
{
	STDataType data;
	struct StackNode* next;
}stnode;

typedef struct Stack //定义栈结构
{
	//记录栈顶
	stnode* top;
	//记录栈内有效数据个数
	int size;
}st;

//初始化栈
void STInit(st* pst);
//入栈
void STPush(st* pst, STDataType x);
//出栈
void STPop(st* pst);
//获取栈顶元素
STDataType STTop(st* pst);
//获取栈内有效数据个数
int STSize(st* pst);
//判断栈是否为空
bool STEmpty(st* pst);
//打印栈内元素
void STPrint(st* pst);
//销毁栈
void STDestroy(st* pst);

4.1 链式栈的声明

Stack.h

typedef int STDataType;

typedef struct StackNode //定义节点结构
{
	STDataType data;
	struct StackNode* next;
}stnode;

typedef struct Stack //定义栈结构
{
	//记录栈顶
	stnode* top;
	//记录栈内有效数据个数
	int size;
}st;

这里如果我们用单链表的形式实现栈的话，单链表头插的时间复杂度为O(1),尾插的时间复杂度为O(N)，所以这里我们需要把单链表的第一个有效节点设置为栈顶，如果想把链表的尾设置尾栈顶的话，那我们这里可能就需要使用双向链表来实现了，本章主要使用单链表来实现栈。

我们在声明链式栈的时候，我们这里使用了两个结构体，其中一个结构体声明链式栈里的数据节点，另一个结构体声明栈的结构，其中里面有个指向栈顶指针，还有一个记录栈内有效数据个数的size，这样我们在获取栈内有效数据个数的时候不需要遍历链表，时间复杂度从O(N)变成O(1)

4.2 链式栈的初始化

Stack.c

void STInit(st* pst)
{
	assert(pst);
	pst->top = NULL;
	pst->size = 0;
}

4.3 链式栈的入栈

Stack.c

void STPush(st* pst, STDataType x)
{
	assert(pst);
	stnode* newnode = (stnode*)malloc(sizeof(stnode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pst->top== NULL)
	{
		pst->top = newnode;
	}
	else
	{
		newnode->next = pst->top;
		pst->top = newnode;
	}
	pst->size++;
}

4.4 链式栈的出栈

Stack.c

void STPop(st* pst)
{
	assert(pst);
	assert(pst->size > 0);
	stnode* next = pst->top->next;
	free(pst->top);
	pst->top = next;
	pst->size--;
}

4.5 链式栈获取栈顶元素

Stack.c

STDataType STTop(st* pst)
{
	assert(pst);
	assert(pst->size > 0);

	return pst->top->data;
}

4.6 链式栈获取栈内有效数据个数

Stack.c

int STSize(st* pst)
{
	assert(pst);
	
	return pst->size;
}

4.7 链式栈判断栈是否为空

Stack.c

bool STEmpty(st* pst)
{
	assert(pst);

	return pst->size == 0;
}

4.8 链式栈打印栈内元素

Stack.c

void STPrint(st* pst)
{
	assert(pst);

	while (!STEmpty(pst))
	{
		printf("%d\n",STTop(pst));
		STPop(pst);
	}
}

4.9 链式栈销毁栈

Stack.c

void STDestroy(st* pst)
{
	assert(pst);
	stnode* pcur = pst->top;
	while (pcur)
	{
		stnode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pst->top = NULL;
	pst->size = 0;
}

4.10 完整代码

Stack.h

//需要用到的库函数的头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int STDataType;

typedef struct StackNode //定义节点结构
{
	STDataType data;
	struct StackNode* next;
}stnode;

typedef struct Stack //定义栈结构
{
	//记录栈顶
	stnode* top;
	//记录栈内有效数据个数
	int size;
}st;

//初始化栈
void STInit(st* pst);
//入栈
void STPush(st* pst, STDataType x);
//出栈
void STPop(st* pst);
//获取栈顶元素
STDataType STTop(st* pst);
//获取栈内有效数据个数
int STSize(st* pst);
//判断栈是否为空
bool STEmpty(st* pst);
//打印栈内元素
void STPrint(st* pst);
//销毁栈
void STDestroy(st* pst);

Stack.c

void STInit(st* pst)
{
	assert(pst);
	pst->top = NULL;
	pst->size = 0;
}

void STPush(st* pst, STDataType x)
{
	assert(pst);
	stnode* newnode = (stnode*)malloc(sizeof(stnode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pst->top== NULL)
	{
		pst->top = newnode;
	}
	else
	{
		newnode->next = pst->top;
		pst->top = newnode;
	}
	pst->size++;
}

void STPop(st* pst)
{
	assert(pst);
	assert(pst->size > 0);
	stnode* next = pst->top->next;
	free(pst->top);
	pst->top = next;
	pst->size--;
}

STDataType STTop(st* pst)
{
	assert(pst);
	assert(pst->size > 0);

	return pst->top->data;
}

int STSize(st* pst)
{
	assert(pst);
	
	return pst->size;
}

bool STEmpty(st* pst)
{
	assert(pst);

	return pst->size == 0;
}

void STPrint(st* pst)
{
	assert(pst);

	while (!STEmpty(pst))
	{
		printf("%d\n",STTop(pst));
		STPop(pst);
	}
}

void STDestroy(st* pst)
{
	assert(pst);
	stnode* pcur = pst->top;
	while (pcur)
	{
		stnode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pst->top = NULL;
	pst->size = 0;
}

5. 疑问

我们发现，我们很多的接口函数只有几行代码，有必要单独写成一个函数吗？比如说出栈，我们直接通过访问结构体进行删除。

其实有必要的，为了规范一定的写法，保持一致性，我们可以通过接口来调用它的函数，不建议自行访问，因为我们不知道设计者在设计top的时候，top是指向栈顶元素还是栈顶元素的下一个位置。

所以，不管再简单，数据结构里面不要直接访问数据，建议调用它的接口方法。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/744694.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

高频面试题基本总结回顾1（含笔试高频算法整理）

高频面试题基本总结回顾1（含笔试高频算法整理）

干货分享&#xff0c;感谢您的阅读&#xff01; &#xff08;暂存篇---后续会删除&#xff0c;完整版和持续更新见高频面试题基本总结回顾&#xff08;含笔试高频算法整理&#xff09;&#xff09; 备注&#xff1a;引用请标注出处&#xff0c;同时存在的问题请在相关博客留言…
阅读更多...
10.XSS绕过之htmlspecialchars()函数

10.XSS绕过之htmlspecialchars()函数

XSS绕过之htmlspecialchars()函数 首先可以测试一下是否将字符被转移成html实体&#xff0c;输入字符测试 1111"<>$点击提交 查看页面元素代码&#xff0c;发现单引号不变&#xff0c;可以利用 重新输入攻击代码&#xff0c;用单引号闭合前面的&#xff0c;进…
阅读更多...
AI智能写作工具,AI写作助手大全

AI智能写作工具,AI写作助手大全

随着人工智能技术的快速发展&#xff0c;AI智能写作工具助手已成为学术研究、内容创作和商业文案等领域的重要辅助工具。它们不仅能够提高写作效率&#xff0c;还能激发创意灵感&#xff0c;为各行各业的专业人士提供了强大的支持。下面小编将为大家全面介绍目前市场上备受瞩目…
阅读更多...
架构是怎样练成的-楼宇监控系统案例

架构是怎样练成的-楼宇监控系统案例

目录 概要 项目背景 原系统设计方案 改进后的设计方案 小结 概要 绝大多数人掌握的架构都是直接学习&#xff0c;慢慢地才能体会到一个架构的好处。架构是一种抽象&#xff0c;是为了复用目的而对代码做的抽象。通过一个项目的改造&#xff0c;理解架构是如何产生的&…
阅读更多...
HTML+CSS 彩色浮雕按钮

HTML+CSS 彩色浮雕按钮

效果演示 实现了一个彩色按钮特效&#xff0c;包括一个按钮&#xff08;button&#xff09;和一个前景色&#xff08;::before&#xff09;。按钮具有四种不同的颜色&#xff0c;当鼠标悬停在按钮上时&#xff0c;前景色会出现渐变效果&#xff0c;并且按钮的颜色、文本阴影和边…
阅读更多...
04 Shell编程之正则表达式与文本处理器

04 Shell编程之正则表达式与文本处理器

目录 4.1 正则表达式 4.1.1 正则表达式概述 1. 正则表达式的定义 2. 正则表达式用途 4.1.2 基础正则表达式 1. 基础正则表达式示例 1. 查找特点字符 2. 利用中括号"[]"来查找集合字符 3. 查找行首"^"与行尾字符"$" 4. 查找任意一个字符".&…
阅读更多...
供应链攻击是什么？

供应链攻击是什么？

随着企业对技术和连接性的依赖日益增加&#xff0c;以及对第三方的普遍依赖&#xff0c;供应链攻击变得越来越普遍。这些攻击旨在通过供应商和商业伙伴损害企业。 供应链攻击可能对企业和组织构成重大威胁&#xff0c;因为它们可能危及它们的安全以及向客户提供的产品和服务的…
阅读更多...
算法训练营day19--530.二叉搜索树的最小绝对差+501.二叉搜索树中的众数+236. 二叉树的最近公共祖先

算法训练营day19--530.二叉搜索树的最小绝对差+501.二叉搜索树中的众数+236. 二叉树的最近公共祖先

一、530.二叉搜索树的最小绝对差 题目链接&#xff1a;https://leetcode.cn/problems/minimum-absolute-difference-in-bst/ 文章讲解&#xff1a;https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF…
阅读更多...
基于KNN的旋转机械故障诊断（MATLAB）

基于KNN的旋转机械故障诊断（MATLAB）

KNN算法又称K-近邻算法&#xff0c;其主要思想是&#xff1a;对于要分类的样本按照一定的相似性度量方法寻找与之最近的K个邻居&#xff0c;计算这K个邻居中类别出现次数最多的那个类作为该样本所属类。其算法步骤如下。 (1)计算待分类样本与训练集中各个数据之间的距离。 (2…
阅读更多...
React 19 新特性集合

React 19 新特性集合

前言&#xff1a;https://juejin.cn/post/7337207433868197915 新 React 版本信息 伴随 React v19 Beta 的发布&#xff0c;React v18.3 也一并发布。 React v18.3相比最后一个 React v18 的版本 v18.2 &#xff0c;v18.3 添加了一些警告提示&#xff0c;便于尽早发现问题&a…
阅读更多...
数学建模--Matlab操作与运算

数学建模--Matlab操作与运算

目录 1.点运算 2.文件介绍 &#xff08;1&#xff09;文件分类 &#xff08;2&#xff09;温度转换 &#xff08;2&#xff09;函数调用 &#xff08;3&#xff09;建模经验 &#xff08;4&#xff09;注意事项 &#xff08;5&#xff09;多个返回值情况 &#xff08;6…
阅读更多...
离线部署OpenIM

离线部署OpenIM

目录 1.提取相关安装包和镜像 2.安装docker和docker-compose 3.依次导入镜像 4.解压安装包 5.执行安装命令 6.PC Web 验证 7.开放端口 7.1IM 端口 7.2Chat 端口 7.3 PC Web 及管理后台前端资源端口 “如果您在解决类似问题时也遇到了困难&#xff0c;希望我的经验分享…
阅读更多...
将深度相机的实时三维坐标数据保存为excel文档（Python+Pyrealsense2+YOLOv8）

将深度相机的实时三维坐标数据保存为excel文档（Python+Pyrealsense2+YOLOv8）

一、如何将数据保存为excel文档 1.excel文件库与相关使用 &#xff08;1&#xff09;导入相应的excel文件库&#xff0c;导入前先要进行pip安装&#xff0c;pip install xlwt import xlwt # 导入用于创建和写入Excel文件的库 (2) 建立一个excel文档&#xff0c;并在第0行写…
阅读更多...
Python | Leetcode Python题解之第198题打家劫舍

Python | Leetcode Python题解之第198题打家劫舍

题目&#xff1a; 题解&#xff1a; class Solution:def rob(self, nums: List[int]) -> int:if not nums:return 0size len(nums)if size 1:return nums[0]first, second nums[0], max(nums[0], nums[1])for i in range(2, size):first, second second, max(first nu…
阅读更多...
读AI新生：破解人机共存密码笔记12人工智能辩论

读AI新生：破解人机共存密码笔记12人工智能辩论

1. 言论 1.1. 对一个人终身职业的威胁&#xff0c;可能会使一个非常聪明的、通常很有思想的人说出一些话&#xff0c;但在进一步分析后&#xff0c;他们很可能希望收回这些话 1.2. 电子计算器在算术方面是“超人”&#xff0c;但是计算器并没有接管世界&#xff0c;因此&…
阅读更多...
IMX6ULL SD卡启动uboot+kernel+rootfs

IMX6ULL SD卡启动uboot+kernel+rootfs

目录 1. 背景说明 2.SD卡启动 2.1准备条件 2.2 对SD卡分区格式化 2.3 制作sd卡镜像 3.效果测试 1. 背景说明 网络上绝大数教程&#xff0c;教大家把uboot烧录到SD卡&#xff0c;然后uboot启动后&#xff0c;通过TFTP下载kernel和设备树&#xff0c;然后通过nfs挂载文件系…
阅读更多...
laravel的日志使用说明

laravel的日志使用说明

文章目录 了解系统的默认支持多个通道时它们的关系如何使用驱动 了解系统的默认支持 Laravel 日志基于「 通道 」和 「 驱动 」的。那么这个通道是干嘛的&#xff1f;驱动又是干嘛的&#xff1f; 通道 &#xff1a; 1.它表示了某种日志格式化的方式&#xff08;或可理解为某个…
阅读更多...
理解CNN模型如何学习

理解CNN模型如何学习

深度学习模型常常被认为是不可解释的。但是人们正在探索不同的技术来解释这些模型内发生了什么。对于图像&#xff0c;由卷积神经网络学习的特征是可解释的。我们将探索两种流行的技术来理解卷积神经网络。 可视化中间层的输出 可视化中间层的输出将有助于我们理解输入图像如何…
阅读更多...
办公软件的答案？ONLYOFFICE 桌面应用编辑器会是最好用的 Office 软件？ONLYOFFICE 桌面编辑器使用初体验

办公软件的答案？ONLYOFFICE 桌面应用编辑器会是最好用的 Office 软件？ONLYOFFICE 桌面编辑器使用初体验

文章目录 &#x1f4cb;前言&#x1f3af;什么是 ONLYOFFICE&#x1f3af; 主要功能介绍及 8.1 新功能体验&#x1f3af; 在线体验&#x1f4dd;最后 &#x1f4cb;前言 提到办公软件&#xff0c;大家最常用的可能就是微软的 Microsoft Office 和国产的 WPS Office。这两款软件…
阅读更多...
使用API有效率地管理Dynadot域名，为文件夹中的域名进行域名停放

使用API有效率地管理Dynadot域名，为文件夹中的域名进行域名停放

关于Dynadot Dynadot是通过ICANN认证的域名注册商&#xff0c;自2002年成立以来&#xff0c;服务于全球108个国家和地区的客户&#xff0c;为数以万计的客户提供简洁&#xff0c;优惠&#xff0c;安全的域名注册以及管理服务。 Dynadot平台操作教程索引&#xff08;包括域名邮…
阅读更多...
最新文章

Copyright @ 2022~2023