Java的Stack类实现List接口真的是个笑话吗

时间:2022-03-12 01:36:51
 
 
今天在网上闲逛时看到了这样一个言论,说“Java的Stack类实现List接口的设计是个笑话”。
 
当然作者这篇文章的重点不是这个,原本我也只是一笑置之,然而看评论里居然还有人附和,说“Java那种Stack的设计作为笑话,差不多可以算公案了”,我就有点不淡定了,为什么、什么时候“作为笑话”的并且“差不多可以算公案”了呢?
 
因此我决定写一篇文章来谈谈这个问题。
 
Java中Stack类的声明
 
首先我们来看看Java中Stack类的声明:
 
public class Stack<E> extends Vector<E>
 
Vector:
 
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable
 
也就是说,Stack定义了标准的push/pop等操作,同时也实现了List和RandomAccess接口。List接口在Java中表示的是一个顺序列表,RandomAccess则在顺序访问的基础上又加上了“随机访问”的约定。一般来说,随机访问的时间复杂度为O(1)。例如数组就是一个“顺序且随机访问”的列表,而链表则是一个“顺序非随机访问”的列表。
 
接口是什么
 
狭义地讲,接口就是一个类所定义的方法(方法名、参数、返回值)。一个类提供了Foo方法,其他类就可以调用它。广义上讲,接口可以理解为一个子系统和其他子系统之间为了交互所做的约定。这里的子系统可能是类,也可以是模块,或其他任何能够可以跟外界产生交互的实体。
 
注意:在Java中,我们可以使用Interface来定义一个接口,Interface不做任何事情,仅仅用来为实现提供“规范”,因此Interface比抽象类更纯粹,抽象层次往往也要更高一些。但是请注意这里的Interface和泛指的“接口”不同,Interface是Java为了更好地支持“针对接口编程”而提供的一种语言机制,即使不用Interface我们也可以很好地做到“针对接口编程”。
 
如果一个类完全遵守一个接口,就可以说这个类“实现”了这个接口。实现一个接口在语言层面是任意的,因为语言只能对语法进行检查,而无法对语意进行检查。例如你可以让People类实现Plant接口,于是这个人就可以随时被当作一颗植物来使用(植物人?)。对动态语言来说,这种情况更加明显:只要一个对象表现出了某种行为特征,那么这个对象就可以被当作另一个对象来使用。人们给动态语言的这种特性起了一个形象化的名字:鸭子类型(Duck Typing)。也就是说,只要一个对象能够“呱呱叫”,那么就完全可以把它当成一只鸭子。
 
但是从设计者的角度来看,一个类实现哪些接口,除了要符合语法之外,更应该符合语意,这样才能让使用这个类的人不至于产生迷惑。
 
因此,“Stack类应不应该实现List接口”是一个语意问题而不是语法问题。要回答这个问题,首先要了解Stack是什么,以及在哪些场景下需要用到它。
 
Stack是什么
 
Stack,栈,是一种所有程序员都很熟悉的数据机构。栈通常是“后进先出”的(LIFO)。作为一个惯例,栈通常具有名为push和pop的2个操作,push操作将一个元素存入栈中(压入),pop操作则相反,将一个元素从栈顶取出(弹出)。
 
栈的应用
 
多数情况用到栈时,仅仅将其当作一个“栈”来使用即可,即只需使用push/pop操作,例如可以用栈来检查括号匹配问题,或计算后缀表达式的值。
 
另一个例子是计算机中的过程调用(procedure call)。在调用一个过程(也称为子过程、函数)之前,需要先将当前帧指针、返回地址压入栈中,然后依次压入各参数,最后执行call指令跳转到目标过程的起始地址继续执行。其栈结构如下图所示。
 
Java的Stack类实现List接口真的是个笑话吗
 
从过程中返回和调用时正好相反:先从栈上将各参数和临时变量弹出(一般直接丢弃),然后执行ret指令跳转到返回地址所在的位置继续执行。
 
随机访问栈
 
到目前为止,程序对栈的操作还只是标准的push/pop操作。但在一个过程的内部,除了要用到push/pop操作之外,可能还需要对栈做随机访问(类似于数组的访问方式)。以上图为例,过程Q中的代码可能要访问参数y1,但又不能丢掉y2,因此不能使用pop操作。
 
事实上,在所有基于栈来实现过程调用的计算机中,编译器都是使用随机访问的方式操作栈上的参数和临时变量的,只有在call和ret时才需要对栈进行push/pop操作。此时的栈对过程来说更像是一个数组。例如过程Q可能通过下面的方式来访问y1:
 
*(SP + )
这里SP是栈指针,它指向栈顶,并且假设y2占用1个机器字长(例如在32位系统中4个字节为一个机器字长)。另外之所以是加1而不是减1,是因为栈是由高地址向低地址增长的,因此y2的地址比y1的小。
 
从这个例子可以看出,根据使用场景的不同,栈有时也需要像数组一样的随机访问方式,在这种情况下,实际上是把栈看成了一个数组。
 
Java的Stack类实现List到底是不是一个笑话
 
从上面的例子可以看出,Stack实现List和RandomAccess接口是完全合理的。如果你需要把它当成一个纯粹的栈来使用,你只需将其看成一个普通的“Stack”实例即可。但如果你需要对其进行随机访问,你可以随时把它当成一个“RandomAccess的List”来使用。这两种情况都有可能会遇到。
 
所以我看了上面的文章和评论后对“Stack实现List是一个笑话”感到非常疑惑,更不明白在什么时候这已经成为了所谓的“公案”了。在我看来,这非常合理,也不会对我正确使用Stack产生任何不良影响。
 
周星驰在《唐伯虎点秋香》里对夺命书生说:谁说没有枪头就捅不死呢?这里借用一下:谁说Stack实现List是个笑话,只是你了解的还不够而已。