基础大扫荡——背包,栈,队列,链表一口气全弄懂

提到数据结构,不得不说数据类型,有人将他们比作分子和原子的关系,我们都知道大自然最小的构成单位是原子,数据类型描述的是原子的内部,如质子、中子的情况,而数据结构是分子,由不同的原子以各种各样的结构组成。

先说Java的数据类型,包括八种基本类型以及对象类型,

内置类型

八种基本类型

值类型

传输时传输值本身

内存随着值传输而变化

扩展类型

对象类型

引用类型

传输时仅传递引用

对象在内存的位置不发生变化

数据结构,是以上这些不同数据类型的数据元素之间以一种或者多种特定关系的集合。

注意关键词:特定关系,集合。

特定关系我们可以理解为数据流动,而集合则是数据以什么样的形式存储。

数据结构之所以是程序语言的基础,是因为它描述了程序如何集合数据,数据如何流动(使用数据和处理数据),而数据流动和集合的方式有很多种,抽象出来最基础的当做砖,然后就像盖大楼一样,不断重用他们,实现更复杂更高级的数据集合和流动的方式,就是算法,所以数据结构和算法是血浓于水的关系。


下面来分析一下可以做砖的,背包,栈,队列是数据结构中数据流动的最佳领路者。

  • 背包Bag,顾名思义,假设我们有一个背包,往里面塞入很多不同颜色的小球,在向外拿的时候,并不会按照我们当时塞进去的顺序,而是无序的,伸手抓到哪个就拿哪个。在数据结构中,背包不支持删除内容,它的特性是可以无序迭代已有内容,因此可以做计算均值,方差,标准差等算法的实现。总结来说背包就是只进不出,内容无序
    • 实现背包的时候要注意,需要设置属性size,方法add()
  • 栈Stack,这不是内存管理中的那个栈的概念,而是一种数据结构。栈的特性是后进先出(LIFO),比较典型的应用就是undo操作、电子邮件和网页多开。我们在word等编辑器中操作时,会用到undo操作,退回上一次操作,查看电子邮件的时候,最新收到的未读邮件总是会排在最上方,而较早的都排在了它的下面。网页多开也是,当我们点击一个超链接的时候,弹出来的页面是这个超链接链入的新页面,而不是最早打开的旧页面,当我们关闭当前页面的时候,看到的页面也是第二新的页面,而不是最早打开的旧页面。所以,我总结栈就是为了保持我们的新鲜感,可以理解为永远追着新闻走,喜新厌旧。
    • 实现栈的时候要注意,需要设置属性size和top(用来指向最新元素),方法push(), pop()
  • 队列Queue,这个就更好理解了,与我们日常排队是相同的原理,当我们排队买票的时候,肯定是先到先得,先来排队的排到前头的先买,后到的排在后面的后买票。所以队列的特性是先进先出(FIFO)系统中我们常提及的任务队列,消息队列正是采用的这种数据结构,先排入的任务或者消息会优先被处理到。
    • 实现队列的时候要注意,需要设置属性size,front(用来指向队头),rear(用来指向队尾),方法enqueue(), dequeue()
    • 注意事项:队列的size是最初设定的,要保证front和rear之间的这一段队列内容的长度,永远小于等于size,但这一段内容看上去是整体向前移动。在入列出列的操作过程中,front和rear的值会越来越大,这个大是没意义的,但会超过size值引发问题,所以我们要用相对位置,
1 front++ 改为 front = (front + 1) % size
2 rear++  改为 rear = (rear + 1) % size

总结一下,背包、栈、队列都是数据结构中描述数据流动方式的,但是各自访问内部元素的顺序和增删情况不同,他们都是属于基础算法。

再重申一下这三种数据结构在存取顺序上,各自的关注点,

背包是不关注顺序,只存不取;

栈是只关注最顶部元素位置,支持存取;

队列是要同时关注队首和队尾两个位置,支持存取。


下面再分析一下稍微复杂的链表结构。

链表是一种实现起来稍微复杂的数据结构,但这种复杂给链表带来了灵活轻巧,相对于以上三种倾向于数据流动的数据结构,链表更关注自身存储数据的结构,但是他更强大。链表的实现与C语言的指针概念很像,链表不依赖具体的内存顺序,也不一定是连续的位置,而是依赖指针的顺序来连接整个链表。所以链表的单位结构是一个value加一个link。value是该单位存储的内容,link是下一个链表单位对象的引用。链表有三种基本操作,

  • 从表头插入,定义表头节点head(head只是“辅助线”,并不是真正存在的元素),新增元素node,
1 node.link = head.link; 
2 head.link = node;
  • 从表尾插入,稍微复杂一点,我们要先用循环找到表尾节点(表尾节点的特点是他的link为null),找到以后,将表尾节点的link从null修改为新增节点,然后新增节点的link设置为null,下面展示一小段关键代码。
1 Node n = head;
2 while(n.link != null){
3     n = n.link;       
4 }
5 n.link = newInsert;
6 newInsert.link = null;
  • 从表头取出,直接取出head.link指向的节点node,
1 head.link = node.link; 
2 node.link = null

由此我们可以看出,实现了这三种基本操作,链表可以自己去实现背包,栈和队列的算法。

  • 表头插入,表头取出,就实现了栈
  • 表头取出,表尾插入,就实现了队列
  • 背包只要插入,无所谓表头插入还是表尾插入。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

数据科学入门必读:如何使用正则表达式?

选自Dataquest 作者:Alex Yang 机器之心编译 参与:Panda 正则表达式对数据处理而言非常重要。近日,Dataquest 博客发布了一篇针对...

346100
来自专栏HTML5学堂

面向对象系列讲解—面向对象的含义&工厂模式

HTML5学堂:在上一篇文章当中,我们把对象进行了基本的解释,本文当中,我将为大家解释什么是面向对象?为何要使用面向对象,而不用面向过程,面向对象又有什么好处,...

29360
来自专栏光变

你所不知道的Java之HashCode

以下内容为作者辛苦原创,版权归作者所有,如转载演绎请在“光变”微信公众号留言申请,转载文章请在开始处显著标明出处。

14400
来自专栏屈定‘s Blog

设计模式--组合模式的思考

组合模式是一种抽象树形结构的模式,其在业务开发中也是一种很有用的设计模式,下面开始分析.

43130
来自专栏java一日一条

Java 8新的时间日期库的20个使用示例

除了lambda表达式,stream以及几个小的改进之外,Java 8还引入了一套全新的时间日期API,在本篇教程中我们将通过几个简单的任务示例来学习如何使用J...

17320
来自专栏MasiMaro 的技术博文

COM学习(一)——COM基础思想

学习微软技术COM是绕不开的一道坎,最近做项目的时候发现有许多功能需要用到COM中的内容,虽然只是简单的使用COM中封装好的内容,但是许多代码仍然只知其然,不知...

17730
来自专栏IT派

程序员们,再不升级 Java 10 就晚了!

正如我们大家都知道的,Java 的最新版本已经来到了10。本文将重点介绍当前正在开发的一些有趣的 Java 新功能。

12320
来自专栏java一日一条

关于 hashCode() 你需要了解的 3 件事

在 Java 中,每一个对象都有一个容易理解但是仍然有时候被遗忘或者被误用的 hashCode 方法。这里有3件事情要时刻牢记以避免常见的陷阱。

6320
来自专栏互联网高可用架构

白话阿里巴巴Java开发手册(编程规约)

36130
来自专栏walterlv - 吕毅的博客

为什么委托的减法(- 或 -=)可能出现非预期的结果?(Delegate Subtraction Has Unpredictable Result)

2017-12-28 02:03

9910

扫码关注云+社区

领取腾讯云代金券