数据结构基础——数组、栈

标签: 数据结构

开发工具与关键技术:数据结构基础
作者:卢雅婷
撰写时间:2020/04/22

之前我已经说过数据结构的分类为数组、栈、队列、链表、树、散列表、堆、图
但也只是粗略的解说一下其中的内容,今天来详细说一下其中的数组和栈。

1、 数组

所谓数组,是有序的元素序列。
数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。
如何了解元素?

释义:定义了个一堆数组,其序列长度为10,数组的名字为a,每个格中存放的都是int类型的元素
例如下面这段代码就是将数组的第一个元素赋值为 1。

int[] data = new int[100];data[0] = 1;
优点:
1、按照索引查询元素速度快
2、按照索引遍历数组方便

缺点:
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加,删除的操作慢,因为要移动其他的元素。
适用场景:
频繁查询,对存储空间要求不大,很少增加和删除的情况。

要想了解栈,先要了解什么是线性表。
哪线性表是什么?
线性表的定义是:由n(n>=)个相同类型数据元素(结点)(a1,a2,……an)其中:n:数据元素的个数,也称表的长度。空表:n=0,记为()。
栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。
线性表有如下特征

  1. 在非空的线性表,有且仅有一个开始结点a1,它没有直接前趋,而仅有一个直接后继a2;
  2. 有且仅有一个终端结点an,它没有直接后继,而仅有一个直接前趋an-1;
  3. 其余的内部节点ai(2<=i<=n-1)都有且仅有一个直接前趋ai-1和一个直接后继
    线性表的基本运算有
  4. 求表长
  5. 遍历
  6. 按编号查找
  7. 按特征查找
  8. 插入
  9. 删除
  10. 排序

2、 栈

栈的定义:
堆栈简称为栈,是限定只能在表的一端进行插入和删除操作的线性表。
在表中,允许插入和删除的一端称作“栈顶”,另一端称作“栈底”。通常将元素插入栈顶的操作作为“入栈”(进栈或压栈),称删除栈顶元素的操作为“出栈”。
(该图片来自于网上)
在这里插入图片描述
栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。

栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。
栈的存储结构:
(1) 顺序栈—采用顺序结构存储
(2) 链栈----采用链式结构存储
在这里插入图片描述
数组和栈的知识点就说到这里,如有不对之处请谅解并提出,我定虚心接纳,感谢阅读。

版权声明:本文为weixin_44538353原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44538353/article/details/106007954

智能推荐

1638 统计只差一个字符的子串数目(动态规划)

1. 问题描述: 给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换一个不同字符以后,是 t 串的子串。换言之,请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。比方说, "computer" 和 "computation"...

websocket基本原理

HTTP中一个request只能有一个response。而且这个response也是被动的,不能主动发起 因此过去的服务端推送信息是通过客户端不停的轮询实现的 websocket是双向通信协议,提供了服务端主动推送信息的能力 需要客户端(浏览器)和服务端同时支持 如果经过代理的话,还需要代理支持,否则有些代理在长时间无通信时会自动切断连接 因此WS为了保证连接不被断掉,会发心跳 WebSocket...

mybatis+ehcache二级缓存

导入jar包 mapper.xml文件开启二级缓存 pojo类实现序列化接口 配置ehcache.xml 测试...

python+opencv实现图像拼接

任务 拍摄两张图片去除相同部分,拼接在一起 原图 结果 步骤 读取两张图片 使用sift检测关键点及描述因子 匹配关键点 处理并保存关键点 得到变换矩阵 图像变换并拼接 代码实现 扩展 这里对右边图像进行变换,右边变得模糊,可以修改代码对左边图像变换 这里只有两张图片拼接,可以封装实现多张图片拼接 可以修改代码实现上下图片的拼接...

python_sklearn机器学习算法系列之AdaBoost------人脸识别(PCA,决策树)

          注:在读本文之前建议读一下之前的一片文章python_sklearn机器学习算法系列之PCA(主成分分析)------人脸识别(k-NearestNeighbor,KNN)         本文主要目的是通过一个简单的小...

猜你喜欢

memmove函数与memcpy函数的模拟实现

memmove函数和memcpy函数都是在内存复制任意类型的,但是它俩也有区别。当源区域和目标区域有重复的,memmove函数会复制缓冲区重叠的部分,而memcpy相反,会报出未知错误。 下面给出两个函数的实现 首先,memmove函数。 实现的基本原理如下图。 具体代码如下: memcpy函数的实现很简单,就直接给出源代码了...

SpringFramework核心 - IOC容器的实现 - 总结

1. 概述 把Spring技术内幕第一章和第二章过了一遍,也做了一些笔记, 对IOC容器的实现有了一定皮毛理解,现在跟着源码再过一遍总结一下IOC容器的初始化,Bean的初始化的过程,做一下总结 ① IOC容器和简单工厂模式 在开始之前,先想想我们平时是怎么使用IOC容器为我们管理Bean的,假设我们要把下面的User类交给IOC容器管理 我们不想关心如何创建一个User对象实例的,仅仅在需要他的...

Python和Django的安装

个人博客导航页(点击右侧链接即可打开个人博客):大牛带你入门技术栈  一、下载并安装Python Python 官方下载地址:http://www.python.org/ftp/python/ 我们这里选择的是 Python 2.7.2 。虽然目前最新版是Python 3.2.2, 但是Django目前还不支持 Python 3.2.2。 安装步骤很简单,双击安装包开...

OpenStack代码贡献初体验

为什么80%的码农都做不了架构师?>>>     OpenStack如今已成为开源云平台中的明星项目,得到广泛关注。OpenStack的优秀出众依赖于众多开发者的努力,在享受其带来的便利与快捷的同时,为其做一份贡献也是一个开发者的义务。  在前段时间的OpenStack的测试过程中,我发现Nova项目中的一个Bug,于是向社区提交了Bug报...