浅谈一下java API设法的一个错误带来的后果引以为戒

你为什么说用linkedlist实现stack完全没有道理呢？

ｌｉｎｋｅｄｌｉｓｔ的优点是在中间插入，删除元素的时间复杂度为Ｏ（１）。而缺点是消耗大量辅助空间。
这个优点对Ｓｔａｃｋ没有用。因此就只有缺点而没有优点了。

而且对ｓｔａｃｋ提供除Ｐｕｓｈ，Ｐｏｐ之外其他的操作也不是什么大问题。毕竟对栈里的数据进行查找，排序是常用操作。需要在栈中间插入或者删除一些元素的需求也不是特别奇怪。像表达式解析经过大幅优化后经常需要这么干。

ｌｉｎｋｅｄｌｉｓｔ缺点是随机访问慢。现在的硬件环境还有谁会在乎几个引用的空间。
再说，linkedlist之外，用数组实现的有序集合，同样要让费空间，这个让费，未必比linkedlist小，而且，增删时还需要反复的从新分配、清理。。。。

首先，辅助空间的消耗是按照空间复杂度来计算的。vector的情况比较复杂，但是通常可以按照O（1）来计算。而linkedlist是O(n)。

第二，我已经说明过是在不考虑Shrink的情况。绝大多数stack是不shrink的，并且对于java来说Shrink的成本并不是很高。虽然时间复杂度是O(n)，但是常数非常小。

第三，linkedlist才会在Pop,push中反复分配，清理每个节点。vector的情况要好得多。

第四，对于JAVA这样的纯引用Stack来说，vector在绝大多数情况下是最优解。

第五，不存在一种数据结构在所有情况中都是最优的。C++大量使用value stack，所以deque适用于大多数情况。Java只有Reference stack，选择vector没有任何问题。而linked list只在极少数极端情况才适用。

讨论数据结构及算法时，请不要泛泛而谈。“几个”，“未必”这样的词不能说明任何问题。具体说明时间复杂度和空间复杂度才有说服力。

这个你还是看一下JDK源码再说吧。


不懂


也是，但是相对于vector那样可能整个数组的从新分配、复制、清理，要好的多。小块的内存声请开销更低。


就凭Vector的同步特征，就可以让它在很多情况下被剔除出局。


不觉得，只要没有随机访问的需求，看不出linked list的致命缺陷。


我是经验主义，仅供参考，不想去说服每一个人。

我看了一下JDK1.5的源代码，没什么太大的问题。我已经说过了，vector的空间复杂度比较复杂，确实有可能比linkedlist大。按照JDK1.5的实现，按照O（1）计算可能不太合理，但是平均情况是linkedlist的1/4（linkedlist是双向链表）。如果开放出Vector(int initialCapacity, int capacityIncrement)构造函数或者从Ｓｔａｃｋ在继承一下，修改capacityIncrement的话，空间复杂度几乎就是Ｏ（１）了。但是Ｐｕｓｈ的时间复杂度会上升。
如有疑义，请详细说明。

同上，反复Pop,Push中，vector并没有反复分配内存。
对于最大size是n，Pop/Push m次的情况来说，基于vector的stack。内存的分配次数为O(log (n))。和Pop/push次数无关。
linkedlist的内存分配次数为O(m)。
m>=n,且通常m远大于n。孰优孰劣很清楚了。
如有疑义，详细说明。

如果是同步的问题的话，应该引入非同步的vector，比如ArrayList。


linked list每次Push/Pop都要重新分配内存这点已经够致命了，而且还有巨大辅助空间的消耗。

为什么CPP里用dequeue而不用vector
因为用Vector有个无法逃避的问题
当size大于预先分配时 会首先申请空间 然后拷贝构造
再释放原有空间
如果你的stack确定大小 的确可以自定义你自己的stack实现

vector的优点在于平均时间复杂度最小
看看STL的代码
Dequeue:

void  push_back(const value_type& __x)
      {
	if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_last - 1)
	  {
	    std::_Construct(this->_M_impl._M_finish._M_cur, __x);
	    ++this->_M_impl._M_finish._M_cur;
	  }
	else
	  _M_push_back_aux(__x);
      }

List:

void  push_back(const value_type& __x)
      { this->_M_insert(end(), __x); }

Vector:

void
      push_back(const value_type& __x)
      {
	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
	  {
	    std::_Construct(this->_M_impl._M_finish, __x);
	    ++this->_M_impl._M_finish;
	  }
	else
	  _M_insert_aux(end(), __x);
      }

_M_insert_aux(end(), __x) 是个很费力气的函数 会分配内存再copy再插入
所以用Dequeue虽然不是最优 但还是适合普遍情况

JAVA里为什么不适合用vector 就是LZ说的原因

Vector is poor choice for stack implementation as all Vector methods are accessible
http://72.14.235.104/search?q=cache:c2JsFWrru2UJ:higheredbcs.wiley.com/legacy/college/koffman/0471467561/ppt/ch05.ppt+stack+linkedlist+or+vector&hl=en&ct=clnk&cd=16&gl=sg

1.C++ stl 里stack的实现类是可以通过第二个模板参数选择的。并非一定是deque。
2.C++的数据结构通常保存Value，而不是Reference。这样的话（a）Copy的成本比较高，（b）vector要求连续内存，所以对于size比较大的Value，以及大数据量不适合。而java只能是Reference，所以Copy的成本并不高。
3.我想说明的是做为stack的底层结构，vector比linkedlist好，不是和deque做比较。通常deque比vector更适合。但有些情况vector更好。但是我找不出来在什么情况下linkedlist比较好。
4.我的前提条件是对stack的push和pop的操作次数远大于stack的最大元素数量的情况。也就是不停的push和pop。这是stack的典型情况。
5.能不能具体说说把vector的methods暴露出来有什么缺点。

对于CPP的情况 你可以GOOGLE一下
JAVA的vector暴露了本不应该属于其具有的API

好激烈的争论啊 不过就喜欢这种气氛