Algs4-1.4.36下压栈的空间成本

1.4.36下压栈的空间成本。解释下表中数据,它显示了各种下压栈的实现的一般空间成本,其中链表的节点为一个静态嵌套类,从而避免非静态嵌套类的开销。
图片
1)基于链表的int元素类型,N个值时需要N个Node,每个Node需要16字节的对象开销+两个8字节的引用,一共32字节,N个Node需要32N字节。

2)基于链表的Integer的元素类型,N个值时需要N个Node和N个Integer,每个Node需要32字节,需要32N字节,一个Integer需要16字节的对象开销+4字节的int+4字节填充共24字节需要24N字节,一共56字节。

3)基于大小可变的数组的int元素类型,N个值时最小数组长度为N,最长数组为4N(达到收缩点时),一个int需要4字节,那么需要4N至16N字节。一个数组对象需要16字节的对象开销和一个int4字节存储长度的开销,一共创建了lg4N个数组对象,共计16lgN至16lg4N字节。最终约4N至16N字节。

4)基于大小可变的数组的Integer元素类型,N个值时最小数组长度为N,最长数组为4N(达到收缩点时),一个Integer需要24字节,一个Integer需要一个8字节的引用指向它,那么一个元素需要32个字节,N个元素需要32N字节。当数组长度为4N时有3N个数组元素没有指向Integer,一个引用8字节,3N个引用一共24N字节,那么需要32N+24N=56N字节。

原文地址:https://www.cnblogs.com/longjin2018/p/9854530.html