探索数据结构：顺序栈与链式栈的原理、实现与应用

✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 栈的定义

栈简单来说就是一种只允许在一端进行操作(插入与删除）的线性表。即栈是严格遵守后进先出（Last In First Out）的数据结构，简称LIFO结构

img

img

  • 栈顶（Top）：线性表允许进行插入删除的那一端。
  • 栈底（Bottom）：固定的，不允许进行插入和删除的另一端。

2. 栈的分类

当我们了解栈的定义之后，我们就能大概知晓其实现方式无非就是顺序表或者单链表。根据其实现方式，我们又能将栈分为顺序栈与链式栈。

img

  • 因为单链表头插的效率O(1)明显比尾差O(N)更高，所以我们用单链表实现栈时最好以链表的头为栈顶。如果一定要以尾节点作为栈顶的话，最好以双向链表来实现。本章实现链表栈时以头节点作为栈顶。

3. 栈的功能

  1. 栈的初始化。
  2. 判断栈是否为空。。
  3. 返回栈顶元素。
  4. 返回栈的大小。
  5. 入栈与出栈。
  6. 打印栈的元素。
  7. 销毁栈。

4. 栈的声明

4.1. 顺序栈

顺序栈的声明需要一个指向一块空间的指针a，指向栈顶下一个元素的top，以及标志栈大小的capacity。

typedef int STDataType;
typedef struct Stack 
{
	STDataType* a;
	int top;		//栈顶指针
	int capacity;	//容量
}Stack;
  • 当然也有实现top指向当前栈顶元素的，只不过这时top初始化要为-1，这样才能在填入元素时刚好指向栈顶元素。

4.2. 链式栈

链式栈的声明只需要一个top指针，以及栈的容量capacity。

typedef struct SListNode
{
	STDataType data;
	struct SListNode* next;
}SListNode;
typedef struct Stack
{
	SListNode* top;
	int size;
}Stack;

5. 栈的功能的具体实现

5.1. 栈的初始化

顺序栈与链式栈的初始化分别与顺序表，链表的初始化大致相同。顺序栈先预先分配一块空间，而链式栈可以先初始为NULL。

5.1.1. 顺序栈
void StackInit(Stack* st)
{
	assert(st);
	st->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (st->a == NULL)
	{
		perror("fail mallic");
		return;
	}
	st->top = 0;
	st->capacity = 4;
}
5.1.2. 链式栈
void StackInit(Stack* st)
{
	assert(st);
	st->top = NULL;
	st->size = 0;
}
5.1.3. 复杂度分析
  • 时间复杂度：无论是顺序栈还是链式栈花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是顺序栈还是链式栈花费空间都是一个固定大小，所以空间复杂度为O(1)

5.2. 判断栈是否为空

判断栈是否为空只需要判断top的指向。

5.2.1. 顺序栈
bool StackEmpty(Stack* st)
{
	return (st->top == 0);
}
5.2.2. 链式栈

只需要判断链表头节点下一个是否为空(NULL）。

bool StackEmpty(Stack* st)
{
	return (st->top == NULL);
}
5.2.3. 复杂度分析
  • 时间复杂度：无论是顺序栈还是链式栈花费判断栈是否为空时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是顺序栈还是链式栈判断栈是否为空花费空间都是一个固定大小，所以空间复杂度为O(1)。

5.3. 返回栈顶元素

因为不知道top指向的是栈顶还是栈顶的下一个元素，所以为了避免歧义，我们单独实现一个函数来获取栈顶元素。

5.3.1. 顺序栈
STDataType StackTop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	return st->a[st->top - 1];
}
5.3.2. 链式栈
STDataType StackTop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	return st->top->data;
}
5.3.3. 复杂度分析
  • 时间复杂度：无论是顺序栈还是链式栈返回栈顶元素花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是顺序栈还是链式栈返回栈顶元素花费空间都是一个固定大小，所以空间复杂度为O(1)

5.4. 返回栈的大小

5.4.1. 顺序栈
int StackSize(Stack* st)
{
	return st->top;
}
5.4.2. 链式栈
int StackSize(Stack* st)
{
	return st->size;
}
5.4.3. 复杂度分析
  • 时间复杂度：无论是顺序栈还是链式栈返回栈的大小花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是顺序栈还是链式栈返回栈的大小花费空间都是一个固定大小，所以空间复杂度为O(1)

5.5. 入栈

5.5.1. 顺序栈

顺序栈在入栈之前需要检查栈是否已满。

void STCheckCapacity(Stack* st)
{
	if (st->top == st->capacity)
	{
		int newCapacity = st->capacity == 0 ? 4 : st->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(st->a, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail\n");
			return ;	
		}
		st->a = tmp;
		st->capacity = newCapacity;
	}
}
void StackPush(Stack* st, STDataType x)
{
	assert(st);
	STCheckCapacity(st);
	st->a[st->top] = x;
	st->top++;
}
5.5.2. 链式栈
SListNode* ListCreat(STDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(STDataType));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}
void StackPush(Stack* st, STDataType x)
{
	assert(st);
	SListNode* newnode = ListCreat(x);
	if (StackEmpty(st))
	{
		st->top = newnode;
	}
	else
	{
		newnode->next = st->top;
		st->top = newnode;

	}
	st->size++;
}
5.5.3. 复杂度分析
  • 时间复杂度：顺序栈支持下标的随机访问并且我们以单链表的头作为栈顶，所以时间复杂度为O(1)。
  • 空间复杂度：顺序栈插入数据可能会扩容，如果以最坏的情况来算，空间复杂度为O(N)。而链式栈增加的空间为固定大小，所以空间复杂度为O(1)。

5.6. 出栈

5.6.1. 顺序栈
void StackPop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	st->top--;
}
5.6.2. 链式栈
void StackPop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	SListNode* next = st->top->next;
	free(st->top);
	st->top = next;
	st->size--;
}
5.6.3. 复杂度分析
  • 时间复杂度：无论是顺序栈还是链式栈出栈花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是顺序栈还是链式栈出栈花费空间都是一个固定大小，所以空间复杂度为O(1)

5.7. 打印栈元素

5.7.1. 顺序栈
void StackPrint(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	for (int i = st->top - 1; i >= 0; i--)
	{
		printf("%d\n", st->a[i]);
	}
}
5.7.2. 链式栈
void StackPrint(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	for (SListNode* top = st->top; top!=NULL; top=top->next)
	{
		printf("%d\n", top->data);
	}
}
5.7.3. 复杂度分析
  • 时间复杂度：无论是顺序栈还是链式栈打印都需要遍历整个栈，所以时间复杂度为O(N)。
  • 空间复杂度：无论是顺序栈还是链式栈花费空间都是一个固定大小，所以空间复杂度为O(1)

5.8. 销毁栈

5.8.1. 顺序栈
void StackDestroy(Stack* st)
{
	assert(st);
	free(st->a);
	st->a = NULL;
	st->top = st->capacity = 0;
}
5.8.2. 链式栈
void StackDestroy(Stack* st)
{
	assert(st);
	SListNode* top = st->top;
	while(top!=NULL)
	{
		SListNode* next = top->next;
		free(top);
		top = next;
	}
	st->size = 0;
}
5.8.3. 复杂度分析
  • 时间复杂度：无论是顺序栈还是链式栈销毁花费时间都是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：无论是顺序栈还是链式栈销毁花费空间都是一个固定大小，所以空间复杂度为O(1)

6. 顺序栈与链式栈的对比与应用

6.1. 对比

对比项顺序栈链式栈
时间效率顺序栈支持下标的随机访问，所以时间效率较高，但是这也超出了栈的定义。如果以链表的头作为栈顶，那么链式栈的时间效率也是不错的。但是每次都需要扩容操作，所以效率略比顺序栈低
空间效率顺序栈的扩容较大可能会造成空间的浪费，但是扩容发生的概率低，平均效率还是较高的。链式栈是按需扩容，所以不会造成空间的浪费，但是定义链表节点需要额外定义指针，所以链表节点占用空间更大

6.2. 应用

栈在我们计算机领域应用广泛，如

  1. 当我们打开网页，将多个页面关闭时，这几个页面也就进入栈中。当我们多次点击返回时，就会依次出栈。
  2. 在我们程序设计中，每次调用一个函数时，都会进入一个栈中。当这个函数结束时，这个函数就会出栈。这个知识点我们将会在C语言中详细阐述。

7. 完整代码

7.1. 顺序栈

7.1.1. stack.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack 
{
	STDataType* a;
	int top;		//栈顶指针
	int capacity;	//容量
}Stack;
void StackInit(Stack* st);//初始化栈
bool StackEmpty(Stack* st);//判断栈是否为空
STDataType StackTop(Stack* st);//返回栈顶元素
int StackSize(Stack* st);//栈的大小
void StackPush(Stack* st, STDataType x);//入栈
void StackPop(Stack* st);//出栈
void StackPrint(Stack* st);//打印
void StackDestroy(Stack* st);//销毁栈
7.1.2. stack.c
#include"Stack.h"
void STCheckCapacity(Stack* st)
{
	if (st->top == st->capacity)
	{
		int newCapacity = st->capacity == 0 ? 4 : st->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(st->a, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail\n");
			return ;	
		}
		st->a = tmp;
		st->capacity = newCapacity;
	}
}

void StackInit(Stack* st)
{
	assert(st);
	st->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (st->a == NULL)
	{
		perror("fail mallic");
		return;
	}
	st->top = 0;
	st->capacity = 4;
}
bool StackEmpty(Stack* st)
{
	return (st->top == 0);
}
STDataType StackTop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	return st->a[st->top - 1];
}
int StackSize(Stack* st)
{
	return st->top;
}
void StackPush(Stack* st, STDataType x)
{
	assert(st);
	SListNode* newnode = ListCreat(x);
	st->a[st->top] = x;
	st->top++;
}
void StackPop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	st->top--;
}
void StackPrint(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	for (int i = st->top - 1; i >= 0; i--)
	{
		printf("%d\n", st->a[i]);
	}
}

void StackDestroy(Stack* st)
{
	assert(st);
	free(st->a);
	st->a = NULL;
	st->top = st->capacity = 0;
}

7.2. 链式栈

7.2.1. stack.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct SListNode
{
	STDataType data;
	struct SListNode* next;
}SListNode;
typedef struct Stack
{
	SListNode* top;
	int size;
}Stack;
void StackInit(Stack* st);//初始化栈
bool StackEmpty(Stack* st);//判断栈是否为空
STDataType StackTop(Stack* st);//返回栈顶元素
int StackSize(Stack* st);//栈的大小
void StackPush(Stack* st, STDataType x);//入栈
void StackPop(Stack* st);//出栈
void StackPrint(Stack* st);//打印
void StackDestroy(Stack* st);//销毁栈
7.2.2. stack.c
void StackInit(Stack* st)
{
	assert(st);
	st->top = NULL;
	st->size = 0;
}

bool StackEmpty(Stack* st)
{
	return (st->top == NULL);
}
STDataType StackTop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	return st->top->data;
}
int StackSize(Stack* st)
{
	return st->size;
}
SListNode* ListCreat(STDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(STDataType));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}
void StackPush(Stack* st, STDataType x)
{
	assert(st);
	SListNode* newnode = ListCreat(x);
	if (StackEmpty(st))
	{
		st->top = newnode;
	}
	else
	{
		newnode->next = st->top;
		st->top = newnode;

	}
	st->size++;
}
void StackPop(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	SListNode* next = st->top->next;
	free(st->top);
	st->top = next;
	st->size--;
}
void StackPrint(Stack* st)
{
	assert(st);
	assert(!StackEmpty(st));
	for (SListNode* top = st->top; top!=NULL; top=top->next)
	{
		printf("%d\n", top->data);
	}
}

void StackDestroy(Stack* st)
{
	assert(st);
	SListNode* top = st->top;
	while(top!=NULL)
	{
		SListNode* next = top->next;
		free(top);
		top = next;
	}
	st->size = 0;
}

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

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

相关文章

JNDI注入原理及利用IDEA漏洞复现

JNDI注入原理及利用IDEA漏洞复现

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【Java、PHP】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收…
阅读更多...
使用Excel创建高效的库存管理表格及优化技巧

使用Excel创建高效的库存管理表格及优化技巧

库存管理对于企业和组织来说至关重要。Excel作为一款功能强大且广泛使用的电子表格软件&#xff0c;为库存管理提供了灵活性和可定制性。本文将进一步扩展之前的内容&#xff0c;详细介绍如何使用Excel创建高效的库存管理表格&#xff0c;并提供一些优化技巧&#xff0c;帮助您…
阅读更多...
FANUC机器人某个轴编码器损坏时进行单轴零点标定的具体方法

FANUC机器人某个轴编码器损坏时进行单轴零点标定的具体方法

FANUC机器人某个轴编码器损坏时进行单轴零点标定的具体方法 前提： FANUC机器人编码器或其线路有损坏，一般先将机器人移动至零点位置，编码器相关部件更换完毕后，直接进行零点标定即可。但是对于突发的状况，这种方法显然是不行的，比如在生产过程中突然发生碰撞导致编码器相…
阅读更多...
【Flutter学习笔记】10.2 组合现有组件

【Flutter学习笔记】10.2 组合现有组件

参考资料&#xff1a; 《Flutter实战第二版》 10.2 组合现有组件 在Flutter中页面UI通常都是由一些低级别组件组合而成&#xff0c;当我们需要封装一些通用组件时&#xff0c;应该首先考虑是否可以通过组合其他组件来实现&#xff0c;如果可以&#xff0c;则应优先使用组合&…
阅读更多...
就业班 第二阶段 2401--3.19 day2 DDL DML DQL 多表查询

就业班 第二阶段 2401--3.19 day2 DDL DML DQL 多表查询

在mysql库里的语句 \G 竖着排列 ; \g 横着排列 数据库用户组成 双单引号单都行 -- sql的注释 创建mysql用户&#xff1a;&#xff08;兼容5.7 8.0 &#xff09; create user root% identified by Qwer123..; grant all on *.* to root%; flush privileges; mysql 5.7 grant …
阅读更多...
ubuntu將en01變成eth0的形式

ubuntu將en01變成eth0的形式

文章目录 前言一、操作步驟1、打開grub文件2、輸入更新指令3、查看結果 二、使用步骤总结 前言 一、操作步驟 1、打開grub文件 使用管理員權限打開&#xff0c;添加新內容 sudo gedit grub2、輸入更新指令 sudo update-grub3、查看結果 使用ifconfig查看是否修改成功&…
阅读更多...
Python使用PaddleSpeech实现语音识别（ASR）、语音合成（TTS）

Python使用PaddleSpeech实现语音识别（ASR）、语音合成（TTS）

目录 安装 语音识别 补全标点 语音合成 参考 PaddleSpeech是百度飞桨开发的语音工具 安装 注意&#xff0c;PaddleSpeech不支持过高版本的Python&#xff0c;因为在高版本的Python中&#xff0c;飞桨不再提供paddle.fluid API。这里面我用的是Python3.7 需要通过3个pip…
阅读更多...
第九节HarmonyOS 常用基础组件31-Toggle

第九节HarmonyOS 常用基础组件31-Toggle

1、描述 组件提供勾选框样式、状态栏样式以及开关样式。 2、子组件 仅当ToggleType为Button时可包含子组件。 3、接口 Toggle(options: { type: ToggleType , isOn?: boolean}) 4、参数 参数名 参数类型 必填 描述 type ToggleType 是 开关的样式。 isOn boole…
阅读更多...
ajax重复请求状态为已取消

ajax重复请求状态为已取消

问题 点击按钮&#xff0c;打开浏览器控制台发现发出了重复请求。 分析&#xff1a; <button onclick"query()">查询</button>错误原因是在form表单中使用了button标签并且增了点击事件&#xff0c;会导致请求被重复发起。 解决办法&#xff1a; &…
阅读更多...
Avue框架实现图表的基本知识 | 附Demo（全）

Avue框架实现图表的基本知识 | 附Demo（全）

目录 前言1. 柱状图2. 折线图3. 饼图4. 刻度盘6. 仪表盘7. 象形图8. 彩蛋8.1 饼图8.2 柱状图8.3 折线图8.4 温度仪表盘8.5 进度条 前言 以下Demo&#xff0c;作为初学者来说&#xff0c;会相应给出一些代码注释&#xff0c;可相应选择你所想要的款式 对于以下Demo&#xff0c…
阅读更多...
填补市场空白，Apache TsFile 如何重新定义时序数据管理

填补市场空白，Apache TsFile 如何重新定义时序数据管理

欢迎全球开发者参与到 Apache TsFile 项目中。 刚刚过去的 2023 年&#xff0c;国产开源技术再次获得国际认可。 2023 年 11 月 15 日&#xff0c;经全球最大的开源软件基金会 ASF 董事会投票决议&#xff0c;时序数据文件格式 TsFile 正式通过&#xff0c;直接晋升为 Apache T…
阅读更多...
【周赛】第385场周赛

【周赛】第385场周赛

&#x1f525;博客主页&#xff1a; A_SHOWY&#x1f3a5;系列专栏&#xff1a;力扣刷题总结录 数据结构 云计算 数字图像处理 力扣每日一题_ 【1】100212.统计前后缀下标对 100212. 统计前后缀下标对 Ihttps://leetcode.cn/problems/count-prefix-and-suffix-pairs-i/ 熟…
阅读更多...
【开源】SpringBoot框架开发知识图谱构建系统

【开源】SpringBoot框架开发知识图谱构建系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 知识图谱模块2.2 知识点模块2.3 学生测评模块2.4 学生成绩模块 三、系统展示四、核心代码4.1 查询知识点4.2 新增知识点4.3 查询知识图谱4.4 查询学生成绩4.5 查询学生成绩 五、免责说明 一、摘要 1.1 项目介绍 基于J…
阅读更多...
5、双亲委派机制

5、双亲委派机制

双亲委派机制指的是&#xff1a;当一个类加载器接收到加载类的任务时&#xff0c;会自底向上查找是否加载过&#xff0c; 再由顶向下进行加载。 详细流程&#xff1a; 每个类加载器都有一个父类加载器。父类加载器的关系如下&#xff0c;启动类加载器没有父类加载器&#xff1…
阅读更多...
sentinel使用控制台实现

sentinel使用控制台实现

1、添加依赖 <!--整合控制台--><dependency> <groupId>com.alibaba.csp</groupId> <artifactId>sentinel-transport-simple-http</artifactId> <version>1.8.0</version></dependency> 此项方法&#xff0…
阅读更多...
将数据转换成xml格式的文档并下载

将数据转换成xml格式的文档并下载

现在有一个实体类对象的集合&#xff0c;需要将它们转换为xml文档&#xff0c;xml文档就是标签集合的嵌套&#xff0c;例如一个学生类&#xff0c;有姓名、年龄等&#xff0c;需要转换成一下效果&#xff1a; <student><age>14</age><name>张三</na…
阅读更多...
python家政服务系统flask-django-php-nodejs

python家政服务系统flask-django-php-nodejs

相比于以前的传统手工管理方式&#xff0c;智能化的管理方式可以大幅降低家政公司的运营人员成本&#xff0c;实现了家政服务的标准化、制度化、程序化的管理&#xff0c;有效地防止了家政服务的随意管理&#xff0c;提高了信息的处理速度和精确度&#xff0c;能够及时、准确地…
阅读更多...
塔楼VR火灾逃生应急安全教育突破了传统模式

塔楼VR火灾逃生应急安全教育突破了传统模式

城镇化的高速发展&#xff0c;给消防安全带来了严峻的挑战&#xff0c;尤其是人员密集的办公场所&#xff0c;如何预防火灾发生&#xff0c;学习火灾成因&#xff0c;减少火灾发生避免不必要的损失&#xff0c;成为安全应急科普的重中之重。 通过模拟真实的办公场所火灾场景&am…
阅读更多...
使用 .NET 和 Teams Toolkit 构建 AI 机器人、扩展 Copilot for Microsoft 365 以及更多

使用 .NET 和 Teams Toolkit 构建 AI 机器人、扩展 Copilot for Microsoft 365 以及更多

作者&#xff1a;Ayca Bas 排版&#xff1a;Alan Wang Teams Toolkit for Visual Studio 帮助 .NET 开发人员为 Microsoft Teams 构建、调试和发布应用程序。我们很高兴向大家宣布&#xff0c;Teams Toolkit for Visual Studio 2022 17.9 版本为 .NET 开发人员提供了许多令人兴…
阅读更多...
如何在Ubuntu系统搭建Excalidraw容器并实现公网访问本地绘制流程图

如何在Ubuntu系统搭建Excalidraw容器并实现公网访问本地绘制流程图

文章目录 1. 安装Docker2. 使用Docker拉取Excalidraw镜像3. 创建并启动Excalidraw容器4. 本地连接测试5. 公网远程访问本地Excalidraw5.1 内网穿透工具安装5.2 创建远程连接公网地址5.3 使用固定公网地址远程访问 本文主要介绍如何在Ubuntu系统使用Docker部署开源白板工具Excal…
阅读更多...
最新文章

Copyright @ 2022~2023