数据结构深入理解--栈

目录

一、栈的定义

二、栈的实现 

        2.1 栈的结构

        2.2 栈的初始化 

        2.3 栈的销毁

        2.3 栈元素的插入

        2.4 栈元素的删除

        2.5 栈顶元素获取

        2.6 栈元素有效个数获取 

        2.7 栈是否为空判断

三、代码总览

        Stack.h

        Stack.c

        测试代码:test.c

四、例题

        例一：

        例二： 

        例三： 

 

一、栈的定义

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

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

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

        9995acf9cd2541fb8574cb24bab7927f.png 

        栈可以这样理解：相信大家都对枪械有一定粗略的了解，咱们就用压子弹来帮助大家进行理解。

        压栈，大家可以想象为压子弹，子弹是一发一发往下压，那压栈就是在容量之内一个数据一个数据往下压。 

        出栈，大家可以理解为子弹射出的过程，即：最后压入的子弹先出。数据最后的先出。

        这就是压栈与出栈的过程，当然也可以压一个出一个，压多个出一个都可以，大家完全就可以把栈当作压子弹和子弹射出。

        好了，基础知识我们已经掌握，那么，我们该用什么结构来实现栈呢？

        通过单链表，双链表还是什么？大家可以在此处进行思考，稍后公布答案。

二、栈的实现 

        上文说到，我们要选择一个结构来实现栈。我们来一一分析一下：

        双链表全称为：带头双向循环链表，用它来实现可以吗？还用说吗？太过于完美当然可以，但是要用两个指针，同学们，一个指针已经困扰大家已久，那两个指针想必是大家不想经历的大恐怖。所以，这个时候咱们把它先列为备胎（实在没办法在想它（在特殊情况下能渣则渣）🐶）。

        单链表全称为：不带头单向不循环链表，大家想单链表找到尾元素麻烦吗？找一遍时间复杂度为O（N）。虽然我们可以反转一下，但是你愿意用吗？要是放两个指针还不如用双链表。

        这个时候怎么办？难道我们要使用双链表？不，绝对不行。这时，数组意外路过，对啊，我们可以用数组。

        数组每次使用前像顺序表一样判断是否开辟空间，在用一个变量size来记录尾，这样不就完美符合要求了。那说干就干吧。打开我们心爱的VS。

        2.1 栈的结构

                栈的结构，可以借鉴一下顺序表，要有数组、容量和栈定元素。结构如下：

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

        2.2 栈的初始化 

                要进行初始化，大家想一想top赋值为多大合适，如果为0，那么0是不是为栈的第一个元素？是不是？答案是：是的。那么，有没有办法不叫top指向数组第一个元素？有，使top的值为-1即可。在后续代码中，我会将top初始化为0（别问，问就是top此时可以当顺序表中的size使用）。代码如下：

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

        2.3 栈的销毁

                在我们今后写代码一定要记住：只要你malloc，realloc一定要free，你创建了就一定要销毁。

                那我们创建了一个栈，那么我们一定要销毁。代码如下：

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//此处记得释放ps指向的数组，不要写成ps！！！
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

                注意事项写在代码里了，一定要记住！！！

        2.3 栈元素的插入

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * sizeof(ps->capacity);
		STDataType* newnode = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));
		if (newnode == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->capacity = newcapacity;
		ps->a = newnode;
	}
	//这里之所以没有封装成一个接口，是因为这里只用一次，其余的都不使用
	ps->a[ps->top] = data;
	ps->top++;
	//这里也可以合二为一
	//ps->a[ps->top++] = data;
}

                此处要点与顺序表类似，就不过多强调。

        2.4 栈元素的删除

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

                此处代码过于简单，那么能不能不把这个封装了，直接写。其实你要是想这么干，你可以试一试，不过提醒一下：可能会出乱子。还是那句话：专业的事专业的人做。

        2.5 栈顶元素获取

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

                对于此代码最后的返回值可能会有人有疑问，我简单解释一下：64f0348468ec4ae69f97fa5f0fd0deab.png   

        2.6 栈元素有效个数获取 

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

                上文说过top初始化为0时可当size来使用，代码简单，不过多解释。

        2.7 栈是否为空判断

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

                注意点：必须包含头文件：stdbool.h。

三、代码总览

        Stack.h

#pragma once
#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* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

        Stack.c

#include"Stack.h"

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * sizeof(ps->capacity);
		STDataType* newnode = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));
		if (newnode == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->capacity = newcapacity;
		ps->a = newnode;
	}
	//这里之所以没有封装成一个接口，是因为这里只用一次，其余的都不使用
	ps->a[ps->top] = data;
	ps->top++;
	//这里也可以合二为一
	//ps->a[ps->top++] = data;
}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//此处记得释放ps指向的数组，不要写成ps！！！
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

        测试代码:test.c

#include"Stack.h"

int main()
{
	Stack p;
	StackInit(&p);
	StackPush(&p, 1);
	StackPush(&p, 2);
	StackPush(&p, 3);
	StackPush(&p, 4);
	while (!StackEmpty(&p))
	{
		printf("%d ", StackTop(&p));
		StackPop(&p);
	}
	StackDestroy(&p);
	return 0;
}

四、例题

        既然明白了，那么来几道题巩固一下吧！

        例一：

        设栈S和队列 Q的初始状态均为空，元素 abcdepg 依次进入栈S。若每个元素出栈后立即进入队列 Q，且7个元素出队的顺序是 bdcfeag，则栈S的容量至少是：

        88e814b0da584e5983d1dcdc5aa93422.png

        例二： 

        若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作，不可能得到的出栈序列是（）。

        A. dcebfa                        B. cbdaef                        C.bcaefd                        D.afedcb

340f8e5b76ce48839dc2686f33b973f5.png

        例三： 

        元素 a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是dcd932288b1246d1a498765de12c4601.png

        好了，我们的学习到现在就结束了，如有疑惑可私信，也可在评论区留言。

完！ 

 

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

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

相关文章

llm.c的Makefile

llm.c的Makefile

源码 CC ? clang CFLAGS -Ofast -Wno-unused-result -Wno-ignored-pragmas -Wno-unknown-attributes LDFLAGS LDLIBS -lm INCLUDES CFLAGS_COND -marchnative# Find nvcc SHELL_UNAME $(shell uname) REMOVE_FILES rm -f OUTPUT_FILE -o $ CUDA_OUTPUT_FILE -o $# N…
阅读更多...
5.神经网络-激活函数

5.神经网络-激活函数

目录 1. 激活函数不是阶跃函数 1.1 激活函数和阶跃函数都是非线性函数 1.2 激活函数不是阶跃函数 2. sigmoid 函数 2.1 sigmoid 函数表达式 2.2 sigmoid 函数 Python 实现 2.4 sigmoid 函数图 3. ReLU 函数 3.1 ReLU 函数表达式 3.2 ReLU 函数 Python 实现 3.4 ReLU…
阅读更多...
Chatgpt的应用场景

Chatgpt的应用场景

文案创作类&#xff1a; 作为一名大型语言模型&#xff0c;ChatGPT可以为使用者提供多种文本处理和文字创作方面的服务&#xff0c;例如&#xff1a; 文本生成和创作 ChatGPT可以基于您提供的主题、关键词或文本段落&#xff0c;生成符合使用者要求的新文本。这些文本可以是文…
阅读更多...
Golang | Leetcode Golang题解之第83题删除排序链表中的重复元素

Golang | Leetcode Golang题解之第83题删除排序链表中的重复元素

题目&#xff1a; 题解&#xff1a; func deleteDuplicates(head *ListNode) *ListNode {if head nil {return nil}cur : headfor cur.Next ! nil {if cur.Val cur.Next.Val {cur.Next cur.Next.Next} else {cur cur.Next}}return head }
阅读更多...
C++的数据结构(二）

C++的数据结构(二）

一、链表的基本概念 链表&#xff08;Linked List&#xff09;是一种物理存储单元上非连续的、非顺序的线性数据结构&#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点&#xff08;链表中每一个元素称为节点&#xff09;组成&#xff0c;节点…
阅读更多...
（二刷）代码随想录第4天|24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点

（二刷）代码随想录第4天|24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点

24. 两两交换链表中的节点 24. 两两交换链表中的节点 - 力扣&#xff08;LeetCode&#xff09; 代码随想录 (programmercarl.com) 帮你把链表细节学清楚&#xff01; | LeetCode&#xff1a;24. 两两交换链表中的节点_哔哩哔哩_bilibili 给你一个链表&#xff0c;两两交换其…
阅读更多...
【计算机网络】物理层传输介质 习题3

【计算机网络】物理层传输介质 习题3

双绞线是用两根绝缘导线绞合而成的&#xff0c;绞合的目的是( )。 A.减少干扰 B.提高传输速度 C.增大传输距离 D.增大抗拉强度 在电缆中采用屏蔽技术带来的好处主要是( ) A.减少信号衰减 B. 减少电磁干扰辐射 C.减少物理损坏 D. 减少电缆的阻抗 利用一根同轴电缆互连主机构成…
阅读更多...
docker安装时报错：Error: Nothing to do

docker安装时报错：Error: Nothing to do

安装docker时报以下错误 解决方法&#xff1a; 1.下载关于docker的相关依赖环境 yum -y install yum-utils device-mapper-persistent-data lvm22.设置下载Docker的镜像源 yum-config-manager --add-repo http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo3…
阅读更多...
Java 常见集合类

Java 常见集合类

集合的整体框架 Java 的集合&#xff0c;也可以叫做容器&#xff0c;根据集合的整体框架可以看出&#xff0c;主要是两大集合接口&#xff1a;第一个是 Collection 接口&#xff0c;主要用来存放单一的元素对象&#xff1b;另一个是 Map 接口&#xff0c;主要用于存储键值对。…
阅读更多...
Linux·基本指令

Linux·基本指令

从本节开始将新开一个关于Linux操作系统的板块&#xff0c;其实Linux也没什么太神秘的&#xff0c;就是一个操作系统(OS)嘛&#xff0c;跟Windows操作系统是一个概念&#xff0c;只不过Windows中的大部分操作都是用光标点击来进行人机交互&#xff0c;但是Linux是通过输入命令行…
阅读更多...
SQLite性能测试（插入）

SQLite性能测试（插入）

最近一直在思考一个问题&#xff0c;SQLite 做到这么轻量级&#xff0c;那它注定不会像 MySql 一样强性能&#xff0c;那么它的性能怎么样呢&#xff1f;并发量多高呢&#xff1f; 官方解释&#xff1a; About SQLite 最大数据库大小&#xff1a;281TB 最大行大小&#xff1…
阅读更多...
俄罗斯方块的代码实现

俄罗斯方块的代码实现

文章目录 首先是头文件的引入部分接下来是一些预处理指令接下来定义了两个结构体&#xff1a;接下来是全局变量g_hConsoleOutput&#xff0c;用于存储控制台输出句柄。之后是一系列函数的声明最后是main函数源码 首先是头文件的引入部分 包括stdio.h、string.h、stdlib.h、tim…
阅读更多...
Neo4j 之安装和 CQL 基本命令学习

Neo4j 之安装和 CQL 基本命令学习

正常使用结构化的查询语言 SQL&#xff08;Structured Query Language&#xff09;较多一些&#xff0c;但是像 Neo4j 这种非结构化的图形数据库来说&#xff0c;就不得不学习下 CQL&#xff08;Cypher Query Language&#xff09;语言了。如果你之前学过 《离散数学》或《图论…
阅读更多...
【北京迅为】《iTOP-3588从零搭建ubuntu环境手册》-第6章 安装Samba

【北京迅为】《iTOP-3588从零搭建ubuntu环境手册》-第6章 安装Samba

RK3588是一款低功耗、高性能的处理器&#xff0c;适用于基于arm的PC和Edge计算设备、个人移动互联网设备等数字多媒体应用&#xff0c;RK3588支持8K视频编解码&#xff0c;内置GPU可以完全兼容OpenGLES 1.1、2.0和3.2。RK3588引入了新一代完全基于硬件的最大4800万像素ISP&…
阅读更多...
Debian安装Redis、RabbitMQ、Nacos

Debian安装Redis、RabbitMQ、Nacos

安装Redis&#xff1a; 启动Redis、开机自启动 sudo systemctl start redis-server #启动sudo systemctl enable redis-server #开机自启 Redis状态(是否在运行) sudo systemctl status redis-server #查看运行状态 redis-cli ping # 客户端尝试连接 安装RabbitMQ&#xff0c;…
阅读更多...
Rust学习笔记（中）

Rust学习笔记（中）

前言 笔记的内容主要参考与《Rust 程序设计语言》&#xff0c;一些也参考了《通过例子学 Rust》和《Rust语言圣经》。 Rust学习笔记分为上中下&#xff0c;其它两个地址在Rust学习笔记&#xff08;上&#xff09;和Rust学习笔记&#xff08;下&#xff09;。 错误处理 pani…
阅读更多...
百问C语言第1问——彻底弄懂define用法

百问C语言第1问——彻底弄懂define用法

系列文章目录 玩转指针专栏 趣味c程序专栏 一.c语言关系操作符练习题(新手必会) 一.c语言常见概念(超全) 一.趣味c程序—关机程序&#xff08;整蛊同学版) 二.趣味c程序—猜数字游戏&#xff08;含干货知识点 三.趣味c程序—打印图形&#xff08;1&#xff09;&#xff08;含干…
阅读更多...
前端笔记-day05

前端笔记-day05

文章目录 01-结构伪类选择器02-结构伪类选择器-公式用法03-伪元素选择器04-盒子模型-组成05-盒子模型-边框线06-盒子模型-单方向边框线07-盒子模型-内边距08-盒子模型-padding多值写法09-盒子模型-尺寸计算10-盒子模型-版心居中11-清除默认样式12-元素溢出overflow13-外边距合并…
阅读更多...
Java | Leetcode Java题解之第83题删除排序链表中的重复元素

Java | Leetcode Java题解之第83题删除排序链表中的重复元素

题目&#xff1a; 题解&#xff1a; class Solution {public ListNode deleteDuplicates(ListNode head) {if (head null) {return head;}ListNode cur head;while (cur.next ! null) {if (cur.val cur.next.val) {cur.next cur.next.next;} else {cur cur.next;}}return…
阅读更多...
E - Yet Another Sigma Problem（ABC字典树）

E - Yet Another Sigma Problem（ABC字典树）

思路&#xff1a;我们可以发现两个字符串的最长公共前缀就是字典树中的最近公共祖先。然而这道题&#xff0c;比如说某个结点是x个字符串的前缀&#xff0c;那么当前结点对答案的贡献为x * (x - 1) / 2&#xff0c;就是x中任选两个字符串组合&#xff0c;因为在这之前&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023