数据结构

数据结构

晨聊数组,温故知新

文章内容参考极客时间《数据结构与算法之美

2020-06-24
54 0

用递归和栈操作逆序一个栈

1.题目一个栈依次压入1,2,3,4,5之后,那么从栈底到栈顶的顺序为:1,2,3,4,5,将这个栈倒置之后,栈底到栈顶的顺序为5,4,3,2,1,整个过程只能使用递归函数来实现,不能用其他数据结构2.解答需要设计两个递归函数,一个是getAndRemoveLastElement,用来返回每次栈底数据,得到之后进行返回,并将之前弹出来的数据重新压入栈中另外一个是reverse,得到栈底元素,再将栈进行倒置,递归进行,直到栈中没有元素时,再将各个栈底i依次压入,实现了导入功能。总的来说还是使用了两个栈的,其中一个是显式的stack,另外递归函数都是在一个栈里面进行返回的,那么要实现倒序功能,就要使stack栈和递归函数栈中的元素顺序是一样的,这样再将递归函数栈里面的元素压入stack栈时,才能实现倒序功能,这道题

2020-03-18
47 0

使用两个栈实现队列

1.题目使用两个栈实现队列的push,poll,peek操作2.解决栈的特点是先进后出,队列的特点是先进先出,使用两个栈可以保证顺序的正确性,一个栈记为stackPush,另一个栈记为stackPop,每次进行push操作时,在stackPush中只需要正常入栈即可,队列进行poll操作时,如果stackPop栈为空,把stackPush栈里面的所有元素全部pop出来,并压入到stackPop栈栈里面,这时stackPop栈的栈顶元素,就是最先进来的元素,只需要返回stackPop.pop()即可,如果队列再一次执行pop,那么再一次返回栈顶。队列的peek操作同样如此,只需要返回stackPop栈的peek()即可代码实现:packagejava1;importjava.util.Stack;/***@Author:hadoo*@Date:2020/3/1718:28*/publiccl

2020-03-17
48 0

设计一个有getMin功能的栈

1.题目实现一个特殊的栈,在实现原有基本功能的基础上,加上返回栈中最小元素的操作2.要求push,pop,getMin操作的时间复杂度都是O(1)自己实现的栈可以使用现成的栈方法3.解答首先我的想法是每一次进行返回栈中最小元素的操作时,将栈中的元素全部pop出来到一个容器中,在这个过程中更新维护一个最小值,然后再把元素全部push会原来的栈中,这种方法虽然可以实现这个功能,但是这是一个非常狗屎的实现方式,首先,每次调用getMin()方法时都要重新创建一个容器,因为上一次方法调用的容易已经被上一次getMin()方法污染,其间可能进行若干次的push和pop操作,这样不能使用同一个数组,其次在进行返回最小值的过程中,要将全部元素来回折腾一遍,效率是非常低的,这种方法直接pass掉。最终使用的方法是在栈进行具体的push和pop操作中,来维护这个最小值,在设计上我们使用两个栈,一个用来存放当

2020-03-16
45 0

使用数组实现循环队列

为了节省空间,这里使用数组实现了更加实用

2020-03-15
40 0
2020-03-15
45 0

彻头彻尾理解ConcurrentHashMap.md

概要ConcurrentHashMap是J.U.C(java.util.concurrent包)的重要成员,他是HashMap的线程安全,支持高效并发的版本,在默认的理想状况下,ConcurrentHashMap可以支持16个线程执行并发写操作以及任意数量线程的读操作,很早就见识过这个数据结构,但是目前对他只是有一个非常肤浅的理解,下面做一个彻头彻尾,死气摆列的总结。前言.关于HashMap存储结构图的理解整理这篇文章的时候在网上看到了结构图的两种版本,如下图:HashMap中创建数组的语句为:table=newEntry[DEFAULT_INITIAL_CAPACITY];数组的每一个下标均存放Entry对象,这个对象中含有指向下一个Entry对象的next指针,所以这样就构成了一个链表,从上面两幅图的表面可以看出,图一中的链表是带有头节点的,图二没有,关于链表是否带有头节点的区别,在上

2020-03-10
51 0

链表的头节点和头指针.md

概述今天在整理HashMap在多线程环境下的死循环问题时,注意到了一个细节,哈希表的形状分别可以是以下两种形式:当然二者都是对的,其中第二种形式也是我头脑里面想象的符合,继续向下探索,因为table数组中,每个下标所在位置都是可以存放一条链表的,链表可以有头节点,也可以没有,那么第一种HashMap的结构就是每条链表都带有一个头节点,第二张图没有头节点。1.抛开上面的不谈,带头节点的链表和不带头节点的链表有何不同?头指针:把指向第一个节点的指针成为头指针头节点:在第一个节点前面附加一个节点,数据域可以不设任何信息,也可以设置一些特殊信息,例如链表的长度等一个链表可以没有头节点,但是不能没有头指针,头指针作为数组的标识,当你想要访问这个链表时,就要通过头指针来获取链表所在位置,知道了头指针,那么链表中所有的节点都可以被访问到2.头节点不是必要的,那么为什么要进入头节点呢?插入操作假设头节点为

2020-03-09
81 0