数据结构——顺序栈和链式栈

目录

引言

栈的定义

栈的分类

栈的功能

栈的声明

1.顺序栈

2.链式栈

栈的功能实现

1.栈的初始化

(1)顺序栈

(2)链式栈

(3)复杂度分析

2.判断栈是否为空

(1)顺序栈

(2)链式栈

(3)复杂度分析

3.返回栈顶元素

(1)顺序栈

(2)链式栈

(3)复杂度分析

4.返回栈的大小

(1)顺序栈

(2)链式栈

(3)复杂度分析

5.元素入栈

(1)顺序栈

(2)链式栈

(3)复杂度分析

6.元素出栈

(1)顺序栈

(2)链式栈

(3)复杂度分析

7.打印栈的元素

(1)顺序栈

(2)链式栈

(3)复杂度分析

8.销毁栈

(1)顺序栈

(2)链式栈

(3)复杂度分析

顺序栈和链式栈的对比

完整代码

1.顺序表

2.链式表

结束语

引言

在学习完链表之后，我们接下来学习数据结构——栈的内容。

栈的定义

栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的有序集合。这种数据结构只允许在栈顶进行添加（push）或删除（pop）元素的操作。换句话说，最后添加到栈中的元素将是第一个被移除的，就像一叠盘子那样，我们只能从上面开始取放盘子。

如图所示：

栈顶（Top）：栈顶是栈中最后添加（push）元素的位置，也是最先被移除（pop）或查看（peek/top）的元素所在的位置。在栈的所有操作中，无论是添加、删除还是查看元素，都是针对栈顶进行的。因此，栈顶是栈中最活跃、最频繁被访问的位置。

栈底（Bottom）：栈底是栈中最早被添加进去的元素所在的位置，也是栈中唯一一个固定不变的位置（除非整个栈被清空）。在栈的常规操作中，栈底元素不会被直接访问，除非是将整个栈的内容倒序输出或者栈被完全清空。因此，栈底在栈的操作中扮演的是一个相对静态的角色。

栈的分类

栈可以分为顺序栈与链式栈。

如下图所示：

顺序栈：

链式栈：

栈的功能

我们要实现的栈的功能如下所示：

1.栈的初始化。
2.判断栈是否为空。
3.返回队头元素。
4.返回栈的大小。
5.元素入栈。

6.元素出栈。
7.打印栈的元素。
8.销毁栈。

栈的声明

1.顺序栈

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

声明如下：

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

2.链式栈

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

当然这里需要链表的声明。

代码如下：

typedef int STDataType;typedef struct SListNode
{STDataType data;struct SListNode* next;
}SLTNode;typedef struct Stack
{// 指向栈顶节点的指针SLTNode* top;int size;
}ST;

栈的功能实现

1.栈的初始化

顺序栈和链式栈都可以先初始为NULL。

(1)顺序栈

顺序栈可以将top设置为-1，capacity设置为0。

代码如下：

//栈的初始化
void STInit(ST* st)
{assert(st);st->a = NULL;st->top = -1;st->capacity = 0;
}
(2)链式栈

链式栈将size设置为0，top设置为NULL。

代码如下：

//栈的初始化
void STInit(ST* st)
{assert(st);st->size = 0;st->top = NULL;
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

2.判断栈是否为空

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

(1)顺序栈

当top=-1则为空。

代码如下：

//判空
bool STEmpty(ST* st)
{assert(st);return st->top == -1;
}
(2)链式栈

判断top是否指向NULL。

代码如下：

//判空
bool STEmpty(ST* st)
{return (st->top == NULL);
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

3.返回栈顶元素

(1)顺序栈
//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);// 断言确保栈不为空（即栈顶索引不小于0）assert(st->top >= 0);return st->a[st->top];
}
(2)链式栈
//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(!STEmpty(st));return st->top->data;
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

4.返回栈的大小

(1)顺序栈

由于在一开始将top设置为-1，需要top+1才能符合需要。

代码如下：

//获取数据个数
STDataType STSize(ST* st)
{assert(st);return st->top + 1;
}
(2)链式栈
//获取数据个数
STDataType STSize(ST* st)
{return st->size;
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

5.元素入栈

注意：入栈需要检查空间是否足够。

(1)顺序栈

由于top设置的是-1，因此需要先腾出空间然后再将新元素x放在栈顶。

代码如下：

//入栈
void STPush(ST* st, STDataType x)
{assert(st);// 注意：由于top初始化为-1，所以满的条件是top == capacity - 1if (st->top == st->capacity - 1){// 如果栈已满，则扩展栈的容量int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail：");return;}st->a = tmp;st->capacity = newcapacity;}// 增加栈顶索引，为新元素腾出空间st->top++;// 将新元素x存储在栈顶位置st->a[st->top] = x;
}
(2)链式栈
//入栈
void STPush(ST* st, STDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");return;}// 新节点的next指向原来的栈顶newnode->next = st->top;// 设置新节点的数据newnode->data = x;// 更新栈顶为新节点st->top = newnode;st->size++;
}
(3)复杂度分析

时间复杂度：由于顺序栈支持下标的随机访问并且我们以单链表的头作为栈顶，因此时间复杂度为O(1)。

空间复杂度：顺序表又可能需要进行扩容处理，最坏的情况是空间复杂度为O(n)。链式表每次入栈固定为一个节点，因此空间复杂度为O(1)。

6.元素出栈

(1)顺序栈
//出栈
void STPop(ST* st)
{assert(st);assert(st->top >= 0);st->top--;
}
(2)链式栈
//出栈
void STPop(ST* st)
{assert(st);assert(!STEmpty(st));// 获取栈顶节点的下一个节点SLTNode* next = st->top->next;free(st->top);// 更新栈顶指针，使其指向新的栈顶节点st->top = next;st->size--;
}
(3)复杂度分析

时间复杂度：由于顺序栈还是链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

7.打印栈的元素

(1)顺序栈
//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));// 从栈顶开始打印，直到栈底（但不包括索引-1）for (int i = st->top; i >= 0; i--){printf("%d ", st->a[i]);}
}
(2)链式栈
//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));for (SLTNode* top = st->top; top != NULL; top = top->next){printf("%d ", top->data);}
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈打印都需要遍历整个栈，因此时间复杂度为O(N)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

8.销毁栈

(1)顺序栈
//栈的销毁
void STDestory(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = -1;
}
(2)链式栈
//栈的销毁
void STDestory(ST* st) 
{assert(st);SLTNode* top = st->top;while (top != NULL){SLTNode* next = top->next;free(top);top = next;}st->size = 0;
}
(3)复杂度分析

时间复杂度：由于顺序栈还是链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

顺序栈和链式栈的对比

顺序栈链式栈
数据结构使用动态数组实现，元素在物理内存中连续存储使用链表实现，元素通过节点和指针连接，内存空间不连续
内存管理栈空间不足时可动态扩容，释放整个栈时一次性释放内存节点内存单独分配和释放，需要遍历链表以释放所有节点内存
时间效率可以通过数组下标直接访问栈内任意位置的元素，但是这不符合栈的定义由于每次都需要扩容操作，所以效率略比顺序栈低
空间效率顺序栈的扩容较大可能会造成空间的浪费内存使用相对灵活，但每个节点需要额外存储指针

完整代码

1.顺序表

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct STDataType
{STDataType* a;int top;int capacity;
}ST;//栈的初始化
void STInit(ST* st);//栈的销毁
void STDestory(ST* st);//入栈
void STPush(ST* st, STDataType x);
//出栈
void STPop(ST* st);//取出栈顶数据
STDataType STTop(ST* st);//判空
bool STEmpty(ST* st);//获取数据个数
STDataType STSize(ST* st);//栈的打印
void STPrint(ST* st);

Stack.c

#include"Stack.h"//栈的初始化
void STInit(ST* st)
{assert(st);st->a = NULL;st->top = -1;st->capacity = 0;
}//栈的销毁
void STDestory(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = -1;
}//入栈
void STPush(ST* st, STDataType x)
{assert(st);// 注意：由于top初始化为-1，所以满的条件是top == capacity - 1if (st->top == st->capacity - 1){// 如果栈已满，则扩展栈的容量int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}st->a = tmp;st->capacity = newcapacity;}// 增加栈顶索引，为新元素腾出空间st->top++;// 将新元素x存储在栈顶位置st->a[st->top] = x;
}//出栈
void STPop(ST* st)
{assert(st);assert(st->top >= 0);st->top--;
}//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(st->top >= 0);return st->a[st->top];
}//判空
bool STEmpty(ST* st)
{assert(st);return st->top == -1;
}//获取数据个数
STDataType STSize(ST* st)
{assert(st);return st->top + 1;
}//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));// 从栈顶开始打印，直到栈底（但不包括索引-1）for (int i = st->top; i >= 0; i--){printf("%d ", st->a[i]);}
}

2.链式表

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;
}SLTNode;typedef struct Stack
{// 指向栈顶节点的指针SLTNode* top;int size;
}ST;//栈的初始化
void STInit(ST* st);//栈的销毁
void STDestory(ST* st);//入栈
void STPush(ST* st, STDataType x);//出栈
void STPop(ST* st);//取出栈顶数据
STDataType STTop(ST* st);//判空
bool STEmpty(ST* st);//获取数据个数
STDataType STSize(ST* st);//栈的打印
void STPrint(ST* st);

Stack.c

#include"Stack.h"//栈的初始化
void STInit(ST* st)
{assert(st);st->size = 0;st->top = NULL;
}//栈的销毁
void STDestory(ST* st) 
{assert(st);SLTNode* top = st->top;while (top != NULL){SLTNode* next = top->next;free(top);top = next;}st->size = 0;
}//入栈
void STPush(ST* st, STDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");return;}// 新节点的next指向原来的栈顶newnode->next = st->top;// 设置新节点的数据newnode->data = x;// 更新栈顶为新节点st->top = newnode;st->size++;
}//出栈
void STPop(ST* st)
{assert(st);assert(!STEmpty(st));// 获取栈顶节点的下一个节点SLTNode* next = st->top->next;free(st->top);// 更新栈顶指针，使其指向新的栈顶节点st->top = next;st->size--;
}//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(!STEmpty(st));return st->top->data;
}//判空
bool STEmpty(ST* st)
{return (st->top == NULL);
}//获取数据个数
STDataType STSize(ST* st)
{return st->size;
}//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));for (SLTNode* top = st->top; top != NULL; top = top->next){printf("%d ", top->data);}
}

结束语

本篇博客简要介绍了一下栈，接下来我们将接着学习与栈有些类似的另一个数据结构——队列。

数据结构——链式队列和循环队列

感谢各位大佬们的支持！！！

求点赞收藏关注！！！

十分感谢！！！

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

怎么管控终端电脑上的移动端口

怎么管控终端电脑上的移动端口

管控终端电脑上的移动端口&#xff0c;尤其是USB等移动端口&#xff0c;是确保企业数据安全和提升网络管理效率的重要手段。 一、使用注册表编辑器禁用USB端口&#xff08;适用于Windows系统&#xff09; 打开注册表编辑器&#xff1a; 同时按下“WinR”组合键&#xff0c;打…
阅读更多...
IPD产品开发流程详细活动图及说明

IPD产品开发流程详细活动图及说明

1、概念阶段 完整见文章后 2、计划阶段 篇幅有限&#xff0c;获取完整阶段活动图以及步骤说明&#xff0c;见下图
阅读更多...
【UE5】Groom毛发系统的基本使用——给小白人添加头发

【UE5】Groom毛发系统的基本使用——给小白人添加头发

目录 效果 步骤 一、准备 二、使用3DsMax制作毛发 三、在UE中给小白人安装毛发 四、修改毛发材质 效果 步骤 一、准备 1. 新建一个第三人称模板工程 2. 在项目设置中&#xff0c;勾选“支持计算蒙皮缓存” 3. 在插件面板中&#xff0c;启用“Groom”和“Alembic Gro…
阅读更多...
API网关之Apache ShenYu

API网关之Apache ShenYu

Apache ShenYu&#xff08;原名Soul&#xff09;是一个开源的API网关&#xff0c;旨在支持高性能、跨语言和云原生架构。它为管理和控制客户端与服务之间的数据流提供了一种高效且可扩展的解决方案。 文档见 Apache ShenYu 介绍 | Apache ShenYu 以下是Apache ShenYu的详细介…
阅读更多...
Open3D mesh 模型锐化

Open3D mesh 模型锐化

目录 一、概述 1.1原理 1.2实现步骤 1.3应用场景 二、代码实现 2.1关键函数 输入参数 输出参数 2.2完整代码 三、实现效果 3.1原始mesh 3.2处理后mesh 3.3数据显示 Open3D点云算法汇总及实战案例汇总的目录地址&#xff1a; Open3D点云算法与点云深度学习案例汇总…
阅读更多...
【大模拟】逻辑回环类

【大模拟】逻辑回环类

区块链 AcWing 3285. 区块链 - AcWing 区块链涉及密码学、哈希算法、拜占庭问题、共识算法、故障模型、网络模型等诸多知识&#xff0c;也在金融等领域有广泛的应用。 本题中&#xff0c;我们需要实现一个简单的区块链系统。 在一个分布式网络中&#xff0c;有 nn 个节点通…
阅读更多...
5G毫米波测试助力突破高频段设备局限，实现高效外场测试

5G毫米波测试助力突破高频段设备局限，实现高效外场测试

作者介绍 一、方案背景 随着业务对带宽需求的不断增加&#xff0c;通信频谱不断向更高频谱延伸&#xff0c;5G毫米波具有丰富的频率资源&#xff0c;是移动通信技术演进的必然方向。下图是ITU的WRC-19会议发布的目前5G所占用频段。 从图中可以看出&#xff0c;在5G毫米波测试中…
阅读更多...
Java基础核心知识学习笔记

Java基础核心知识学习笔记

方法重载 请记住下面重载的条件 方法名称必须相同。参数列表必须不同&#xff08;个数不同、或类型不同、参数类型排列顺序不同等&#xff09;。方法的返回类型可以相同也可以不相同。仅仅返回类型不同不足以成为方法的重载。重载是发生在编译时的&#xff0c;因为编译器可以根…
阅读更多...
【计算机网络】网络版本计算器

【计算机网络】网络版本计算器

此前我们关于TCP协议一直写的都是直接recv或者read&#xff0c;有了字节流的概念后&#xff0c;我们知道这样直接读可能会出错&#xff0c;所以我们如何进行分割完整报文&#xff1f;这就需要报头来解决了&#xff01; 但当前我们先不谈这个话题&#xff0c;先从头开始。 将会…
阅读更多...
第二十三节、血量更新逻辑的实现

第二十三节、血量更新逻辑的实现

一、创建代码 引入命名空间 using UnityEngine.UI; 调用UI必须有这个代码 二、ScriptObject类 1、是一个持久化存储文件的类型 接收所有的事件方法 先继承SO类&#xff0c;然后创建项目菜单 2、进行订阅 放入事件类&#xff0c;关联代码&#xff0c;即可进行广播 传递给这…
阅读更多...
蓝桥杯2021第十二届蓝桥杯青少年组省赛试题真题

蓝桥杯2021第十二届蓝桥杯青少年组省赛试题真题

带我去看题解&#xff01;&#xff01;&#xff01; 带我去看题单&#xff01;&#xff01;&#xff01; 目录 第一题&#xff1a;[2021第十二届蓝桥杯青少年组省赛] 字符串 题目背景 题目描述 输入格式 输出格式 输入输出样例 第二题&#xff1a;[2021第十二届蓝桥杯…
阅读更多...
AI + 3D 机器人视觉领域综合资源库

AI + 3D 机器人视觉领域综合资源库

随着人工智能技术的不断发展，3D 机器人视觉领域已经成为了一个备受关注的研究方向。在这个领域中，研究者们致力于探索如何让机器人更好地理解三维空间，从而实现更加智能和灵活的操作。为了方便大家学习和研究，这里介绍一个全面的资源库——Awesome Robotics 3D，它汇集了最…
阅读更多...
Ajax技术详解

Ajax技术详解

Ajax简介 Ajax 即 "Asynchronous Javascript And XML"&#xff08;异步 JavaScript 和 XML&#xff09;&#xff0c;是指一种创建交互式、快速动态应用的网页开发技术&#xff0c;无需重新加载整个网页的情况下&#xff0c;能够更新页面局部数据的技术。 为什么要使…
阅读更多...
Markdown中使用 LaTeX 绘图 -- TikZ

Markdown中使用 LaTeX 绘图 -- TikZ

Markdown中使用 LaTeX 绘图 -- TikZ 1 介绍1.1 概述1.2 与其他图包对比 2 示例 & 学习[The TikZ and PGF Packages](https://tikz.dev/)[Graphics with TikZ in LaTeX](https://tikz.net/)[TikZ PGF Manual](https://www.bu.edu/math/files/2013/08/tikzpgfmanual.pdf)[在 …
阅读更多...
【从Qwen2,Apple Intelligence Foundation,Gemma 2,Llama 3.1看大模型的性能提升之路】

【从Qwen2,Apple Intelligence Foundation,Gemma 2,Llama 3.1看大模型的性能提升之路】

从早期的 GPT 模型到如今复杂的开放式 LLM&#xff0c;大型语言模型 (LLM) 的发展已经取得了长足的进步。最初&#xff0c;LLM 训练过程仅侧重于预训练&#xff0c;但后来扩展到包括预训练和后训练。后训练通常包括监督指令微调和校准&#xff0c;这是由 ChatGPT 推广的。 自 …
阅读更多...
机器学习：逻辑回归处理手写数字的识别

机器学习：逻辑回归处理手写数字的识别

1、获取数据, 图像分割该数据有50行100列&#xff0c;每个数字占据20*20个像素点&#xff0c;可以进行切分,划分出训练集和测试集。 import numpy as np import pandas as pd import cv2 imgcv2.imread("digits.png")#读取文件 graycv2.cvtColor(img,cv2.COLOR_BGR2G…
阅读更多...
LVS负载均衡群集-DR模式

LVS负载均衡群集-DR模式

一、负载均衡群集 1.数据包流向分析 客户端发送请求到 Director Server&#xff08;负载均衡器&#xff09;&#xff0c;请求的数据报文&#xff08;源 IP 是 CIP,目标 IP 是 VIP&#xff09;到达内核空间。Director Server 和 Real Server 在同一个网络中&#xff0c;数据通过…
阅读更多...
深度学习基础—Softmax回归

深度学习基础—Softmax回归

通常对于二分类问题&#xff0c;大家熟知的模型就是logistic回归。那么对于多分类问题呢&#xff1f;如果要多分类&#xff0c;我们可以在网络的最后一层建立多个神经元&#xff0c;每个神经元对应一个分类的输出&#xff0c;输出的是某一个分类的概率&#xff0c;这些概率之和…
阅读更多...
写给大数据开发：如何优化临时数据查询流程

写给大数据开发：如何优化临时数据查询流程

你是否曾因为频繁的临时数据查询请求而感到烦恼&#xff1f;这些看似简单的任务是否正在蚕食你的宝贵时间&#xff0c;影响你的主要工作&#xff1f;如果是&#xff0c;那么这篇文章正是为你而写。 目录 引言&#xff1a;数据开发者的困境问题剖析&#xff1a;临时数据查询的…
阅读更多...
小程序开发与发布指南：API、协同工作、版本管理与运营数据

小程序开发与发布指南：API、协同工作、版本管理与运营数据

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023