数据结构中的表、栈和队列

本文介绍数据结构中常用的表、栈和队列。以及Java中ArraryList与LinkedList的区别与选择,栈与队列的概念以及栈的应用以及队列的应用。

 

数据结构中的表

Java中增强的for循环

这段代码对于任何实现了Iterable接口的对象都可以起作用。

而对于数组:

参考:http://docs.oracle.com/javase/specs/jls/se8/html/jls-14.html#jls-14.14.2

 

关于ArrayList和LinkedList的选择

ArrayList底层是用数组实现的,LinkedList则是用双向列表。ArrayList的查找和修改修很快(get和set),都是常数时间(直接修改数组对应索引的值即可),但是都说LinkedList的插入和删除很快,的确,如果是知道结点的位置,插入和删除确实很快,常数时间就可以。但是,在插入前,如果需要先遍历找到结点,这是一个跟N有关的操作。源码中是node(inde index)方法,它是首先判断index的与中间位置的关系,在前半段就通过头结点来进行查找,在后半段就通过尾结点进行查找,确实比ArrayList移动数据快,但也不是常数时间的操作。具体可以查看stackoverflow上的问题:when-to-use-linkedlist-over-arraylist

总结如下:

对于LinkedList:

  1. get(int index) is O(n/4) average
  2. add(E element) is O(1)
  3. add(int index, E element) is O(n/4) average, but O(1) when index = 0 <— main benefit of LinkedList
  4. remove(int index) is O(n/4) average
  5. Iterator.remove() is O(1) <— main benefit of LinkedList
  6. ListIterator.add(E element) is O(1) <— main benefit of LinkedList

Note: O(n/4) is average, O(1) best case (e.g. index = 0), O(n/2) worst case (middle of list)

对于ArraryList:

  1. get(int index) is O(1) <— main benefit of ArrayList
  2. add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
  3. add(int index, E element) is O(n/2) average
  4. remove(int index) is O(n/2) average
  5. Iterator.remove() is O(n/2) average
  6. ListIterator.add(E element) is O(n/2) average

Note: O(n/2) is average, O(1) best case (end of list), O(n) worst case (start of list)

 

关于ArrayList和LinkedList,修改list立马抛出异常

AbstactList中有一个int值modCount,对它的注释是:

可以看到这个值的作用就是记录那些对list的尺寸(大小)有了改动或者对list内部进行了改动导致iterations不能正确执行的修改次数,而在ArrayList和LinkedList的clear()、add()、remove()、sort()等对这个值都进行了modCount++,在Iterator中的next()方法中,会首先执行checkForComodification()方法:

所以只要修改了list,立马就会抛出异常。

 

Java中的ArrayList

一个是放数据的数组,一个是代表当前数据数量的整型。

再贴几个常用的方法的具体实现:

 

Java中的LinkedList

用到的数据结构,可以看到其实是一个双向链表。

分别代表头指针和尾指针。

贴一下常用方法的实现:

LinkedList还提供了快速获取头尾结点,或者是remove头尾结点的方法。removeFirst、removeLast、getFirst、getLast、addFirst、addLast。。。等等,源码不难,理解了这几点,都可以看懂。

 

数据结构中的

所谓栈,就是一种LIFO(last-in-first-out)表,在Java中是通过继承Vector实现的,主要添加了几个操作让它成为一个栈:

可以看到所有方法都是同步的(addElement()是同步的),方法的实现也都是用的Vector里的方法(好像Vector是是JDK1.0的遗留产物了,是不是不推荐用了?而且继承Vector,那不是很多跟栈不相关的方法也都可以访问到?)。

 

栈的应用

1.平衡符号
就是判断左右括号是否可以闭合:

做一个空栈。读入字符直到文件结尾。如果字符是一个开放符号(左边),则将其推入栈中。如果字符是一个封闭符号,则当栈空是报错。否则,将栈元素弹出。如果弹出的符号不是对应的开放符号,则报错。在文件结尾,如果栈非空则报错。

2.后缀表达式
即逆波兰表示法,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

解算方法:
即逆波兰表示法,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

3.中缀到后缀的转换
所谓中缀,就是我们正常时候的表达式,转换方式也可以借助栈来实现:

从左到右遍历中缀表达式的每个操作数和操作符。当读到操作数时,立即把它输出,即成为后缀表达式的一部分;若读到操作符,判断该符号与栈顶符号的优先级,若该符号优先级高于栈顶元素,则将该操作符入栈,否则把栈中运算符弹出并加到后缀表达式尾端,直到遇到优先级低于该操作符的栈元素,然后把该操作符压入栈中。如果遇到”(”,直接压入栈中,除非正在处理“)”否则“(”不会从栈中弹出,如果遇到一个”)”,那么就将直到“(”的所有栈元素弹出并加到后缀表达式尾端,但左右括号并不输出。最后,如果读到中缀表达式的尾端,将栈元素依次完全弹出并加到后缀表达式尾端。

例如a+b*c+(d*e+f)*g 可以转成 abc*+de*f+g*+; 1 + (( 2 + 3)* 4 ) – 5可以转成123+4*+5-

4.方法调用

递归就是不停的将方法压到方法栈中,到达结束条件再一个个弹出来。

 

数据结构中的队列

所谓队列就是FIFO(first-in-first-out)的表,Java中的LinkedList实现了Queue,可以用Queue接口来窄化LinkedList的方法,Queue queue = new LinkedList(),这样就只能访问Queue中的方法。主要有以下几个方法:

 

队列的应用

1.操作系统的各种数据缓冲区的先进先出管理,应用系统中的各种事件排队管理等等。

2.判断回文。所谓回文就是一个字符序列以中间字符基准两边字符完全相同。解决方法可以将字符逐个分别放入队列和栈中,依次弹出,看是否相等,如果全部相等则是回文。

Telegram频道已经开通,关注flyzythink,随手分享正能量,了解VPS优惠与补货
Telegram群组已经开通,加入flyzy小站,FREE TO TALK
搬瓦工用户交流TG群,加入搬瓦工用户交流群,畅聊搬瓦工
VPS交流群1(已满):780593286 flyzy小站
VPS交流群2:729726961 flyzy小站
搬瓦工交流群(搬瓦工用户推荐):938957834 flyzy小站
搬瓦工补货通知群:618922256 搬瓦工补货通知群
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注