动画:动画从零学编程之 “栈” 你掌握这些必备了吗?

2023-11-21 05:10

本文主要是介绍动画:动画从零学编程之 “栈” 你掌握这些必备了吗?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述作者 | 小鹿
来源 | 小鹿动画学编程


写在前边

对于栈的认识,相信每个学习数据结构的小伙伴多多少少有一定的认识和了解。很多刚刚学习的小伙伴说学习数据结构在实际中没怎么见到应用,那是因为你没有去仔细的观察,而且像栈这常用到的数据结构通常会使用在实际开发中,比如:表达式的运算、花括号的匹配以及浏览器的前进后退等等很多。

这些实际开发的实现如果不去研究,你永远不知道数据结构在实际中的应用,当你学习完今天的栈数据结构时,然后去研究下实际中已经使用到的应用,才能让你在今后的实际开发中用到栈这种数据结构,从而使你的开发更加灵活、多变。


思维导图

这篇文章将要学习到的内容。

在这里插入图片描述

1、基本常识

1.1 什么是栈

我们用一种最简单的生活常识描述一下,比如我们往柜子里放东西,先放的东西是需要放到柜子最里边,后放的东西在柜子的最外边;如果我们要取东西,先要取柜子最外边的东西,才能取到柜子最里边的东西。这种先进后出,后进先出的结构称为“栈”。
在这里插入图片描述

1.2 栈的特点

“先进后出,后进先出”。

1.3 栈的操作

栈的操作就两种,分别为出栈和入栈。那我们上边的例子,我们往柜子里放东西的过程称为入栈;我们在柜子里拿东西的过程称为出栈
在这里插入图片描述

PS:柜子只有一个出口和入口,而且出口和入口是一样的。如果两端都有开口,就变成了队列,后期的文章会讲到。

2、栈的实现

我们前边的文章也讲过,所有的数据结构基本都是由数组和链表演化而来的,所以今天讲的栈这种数据结构也不例外。

栈的实现主要有两种,一种是数组的实现,叫做顺序栈,另外一种是链表的实现,叫做链式栈。如下:

2.1 顺序栈

在这里插入图片描述

2.2 链表栈

在这里插入图片描述

2.3 代码实现

顺序栈

/*** 功能:基于数组的顺序栈* 公众号:一个不甘平凡的码农* @author:小鹿**/
public class ArrayStack {private String[] items;  // 数组private int count;       // 栈中元素个数private int n;           // 栈的大小// 初始化数组,申请一个大小为 n 的数组空间public ArrayStack(int n) {this.items = new String[n];this.n = n;this.count = 0;}/*** 功能:入栈* 说明:数组入栈的入口为数组尾部* @param item :入栈数据元素* @return:是否入栈成功*/public boolean push(String item) {// 数组空间不够了,直接返回 false,入栈失败。if (count == n) return false;// 将 item 放到下标为 count 的位置items[count] = item;//数组长度+1++count;//入栈成功return true;}/*** 功能:出栈* * @return:返回出栈元素*/public String pop() {// 栈为空,则直接返回 nullif (count == 0) return null;// 返回下标为 count-1 的数组元素String tmp = items[count-1];//数组长度-1--count;//返回出栈数据元素return tmp;}
}

链式栈


/*** 功能:基本链表的链式栈,入栈、出栈、输出栈* @author : 小鹿* 公众号:一个不甘平凡的码农*/
public class StackBasedLinkedList {//定义栈顶指针private Node top = null;//定义栈结点private static class Node {//栈结点数据域private int data;//栈结点指针域private Node next;//构造函数public Node(int data, Node next) {this.data = data;this.next = next;}//get 获取数据域方法public int getData() {return data;}}/*** 功能:入栈* @param value:要入栈的数据元素*/public void push(int value) {//创建一个栈结点 Node newNode = new Node(value, null);// 判断栈是否为空if (top == null) {//如果栈为空,就将入栈的值作为栈的第一个元素top = newNode;} else {//否则插入到top栈结点前(所谓的就是单链表的头插法)newNode.next = top;top = newNode;}}/*** 功能 : 出栈* @return: -1 为栈中没有数据*/public int pop() {// 如果栈的最顶层栈结点为null,栈为空if (top == null) return -1;//否则执行出栈操作,现将栈顶结点的数据元素赋值给 Valueint value = top.data;//将 top 指针向下移动top = top.next;//返回出栈的值return value;}	/*** 功能:输出栈中所有元素*/public void printAll() {//将栈顶指针赋值给pNode p = top;//循环遍历栈(遍历单链表)while (p != null) {System.out.print(p.data + " ");//指向下一个结点p = p.next;}System.out.println();}
}

3、栈的性能

我们从上边学到了栈的基本结构和特点,还有栈的基本操作。如果我们学习一种数据结构,主要分析它的性能如何。还记得怎么分析数据结构性能吗?主要从两方面入手,第一,时间效率(时间复杂度);第二,空间上的消耗(空间复杂度)。我们就从以上两个方面分析一下栈这种数据结构的性能。


3.1 时间复杂度

时间上的消耗主要分析栈的操作所消耗的时间,我们共两种操作,入栈和出栈,其实在数组中中,我们操作尾部的数据就相当于入栈和出栈,直接根据下标取得相应的元素就好(JS 中数组的 pop 和 push 方法),所以时间复杂度是 O(1)。


3.2 空间复杂度

空间复杂度的判断是所需要开辟的临时空间,顺序栈和链式栈只需要大小为 n 的空间就可以,入栈和出栈需要一个临时空间来存储变量,空间复杂度为 O(1)。


3.3 栈的动态扩容

大家有没有想过这样一种情况,如果栈满的时候,再进行入栈操作,栈内就放不下了,我们需要动态扩容。主要是顺序栈的动态扩容比较麻烦,和我么你之前的数组的文章动态扩容一样的,对于动态扩容的性能,可以自己尝试一下。可以根据之前的文章来分析《佩奇学编程 | 复杂度分析原来这么简单》。


4、栈的实际应用

既然我们把栈的性能分析透了,理解透了,那么我们看看栈在实际中有哪些应用吧。


4.1 应用一 :栈在函数中的应用

函数我们每个人再熟悉不过了,你是不是很纳闷,栈怎么会在函数中能够应用的到呢,我学了这几年函数,我咋不知道函数中还有栈的操作。

加入我们程序开始执行代码,执行到我们声明的函数时,计算机内部会发生什么呢?首先,会为该函数开辟一块临时的内存空间,这块内存空被组织成“栈”这种数据结构,作用主要用来存储函数内部声明的临时变量。

每执行一个函数,系统就将函数中的临时变量组织成栈帧,执行入栈操作,当函数被调用完成的时候,临时变量已经用不到了,所以要在内存中释放,执行出栈操作。如以下函数:

function main(){let i = 0;let j = 1;i++;j++;console.log(i+j)
}
main();

具体的动画如下:
在这里插入图片描述
我们这时要想一个问题,那为什么函数会使用栈这种数据结构呢,为什么不用队列、链表或者其他数据结构?全体注意,重点来了,以后分析其他的问题也用到一下的方法分析。

因为函数调用的执行顺序符合后进者先出,先进者后出的特点。

比如函数中的局部变量声明的时间顺序,早先定义的变量在内存中保存的时间长,后定义的变量在内存中保存的时间短,所有有一个先后的问题。我们再去脑海中把这种问题的特点抽象成数据结构,只有使用“栈”结构,才符合这种问题。


4.2 栈在表达式中应用

计算机中数字的运算也是使用栈这种数据结构的,我们举个例子,我们要计算如下表达式:

1 + 2 × 4 - 6

如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。动画如下:
在这里插入图片描述

4.3 其他应用

关于栈的应用,还有很多,比如花括号的匹配问题,有关练习去 LeedCode 实践。这里就不多举例子。


❤️ 不要忘记留下你学习的脚印 [点赞 + 收藏 + 评论]

一切看文章不点赞都是“耍流氓”,嘿嘿ヾ(◍°∇°◍)ノ゙!开个玩笑,动一动你的小手,点赞就完事了,你每个人出一份力量(点赞 + 评论)就会让更多的学习者加入进来!非常感谢! ̄ω ̄=


作者Info:

【作者】:小鹿

【原创公众号】:小鹿动画学编程。

【简介】:和小鹿同学一起用动画的方式从零基础学编程,将 Web前端领域、数据结构与算法、网络原理等通俗易懂的呈献给小伙伴。先定个小目标,原创 1000 篇的动画技术文章,和各位小伙伴共同努力一起学习!公众号回复 “资料” 送一从零自学资料大礼包!

【转载说明】:转载请说明出处,谢谢合作!~

这篇关于动画:动画从零学编程之 “栈” 你掌握这些必备了吗?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/400032

相关文章

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同

PyCharm接入DeepSeek实现AI编程的操作流程

《PyCharm接入DeepSeek实现AI编程的操作流程》DeepSeek是一家专注于人工智能技术研发的公司,致力于开发高性能、低成本的AI模型,接下来,我们把DeepSeek接入到PyCharm中... 目录引言效果演示创建API key在PyCharm中下载Continue插件配置Continue引言

最好用的WPF加载动画功能

《最好用的WPF加载动画功能》当开发应用程序时,提供良好的用户体验(UX)是至关重要的,加载动画作为一种有效的沟通工具,它不仅能告知用户系统正在工作,还能够通过视觉上的吸引力来增强整体用户体验,本文给... 目录前言需求分析高级用法综合案例总结最后前言当开发应用程序时,提供良好的用户体验(UX)是至关重要

基于Python实现PDF动画翻页效果的阅读器

《基于Python实现PDF动画翻页效果的阅读器》在这篇博客中,我们将深入分析一个基于wxPython实现的PDF阅读器程序,该程序支持加载PDF文件并显示页面内容,同时支持页面切换动画效果,文中有详... 目录全部代码代码结构初始化 UI 界面加载 PDF 文件显示 PDF 页面页面切换动画运行效果总结主

轻松掌握python的dataclass让你的代码更简洁优雅

《轻松掌握python的dataclass让你的代码更简洁优雅》本文总结了几个我在使用Python的dataclass时常用的技巧,dataclass装饰器可以帮助我们简化数据类的定义过程,包括设置默... 目录1. 传统的类定义方式2. dataclass装饰器定义类2.1. 默认值2.2. 隐藏敏感信息

C#反射编程之GetConstructor()方法解读

《C#反射编程之GetConstructor()方法解读》C#中Type类的GetConstructor()方法用于获取指定类型的构造函数,该方法有多个重载版本,可以根据不同的参数获取不同特性的构造函... 目录C# GetConstructor()方法有4个重载以GetConstructor(Type[]

Qt QWidget实现图片旋转动画

《QtQWidget实现图片旋转动画》这篇文章主要为大家详细介绍了如何使用了Qt和QWidget实现图片旋转动画效果,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、效果展示二、源码分享本例程通过QGraphicsView实现svg格式图片旋转。.hpjavascript