关于栈和队列
来源：8-1 什么是优先队列
哈hhh哈
2018-11-15
bobo老师，有一个小问题问您，就是Queue是一个抽象数据类型，要实例化必须调用底层实现Queue的结构 比如 Queue q = new LinkedList(); 我查了一下为什么，我理解的是Queue可以有多种底层数据结构实现，java就提取出Queue的一些抽象特点，讲Queue设计成一个接口，定义为抽象数据类型，请问老师抽象数据类型和抽象数据结构具体的关联是不是就是 java把这些抽象数据结构定义成了抽象数据类型，另外java实现Stack可以使用Stack<> stack = new Stack<>()来实例化一个Stack，说明实例化Stack的底层数据结构就是Stack，那Stack是不是不是抽象数据类型呢？这就很奇怪，明明和Queue功能性虽然有先出和后出的差别 不过感觉功能性和结构很相似啊 而且Stack也可以用底层数据结构来实现啊，为什么实例化的时候Stack s = new LinkedList();，就是错误的呢？感谢老师读了这么长。。这个问题从第二章的时候就出现了，一直思考却不得解
1回答
-
大赞！非常非常好的问题！
首先，从逻辑上讲，栈也是一种抽象数据结构。从这个课程你也应该已经接触了，我们既可以使用动态数组实现栈，也可以使用链表实现栈。动态数组和链表才是底层具体数据结构，栈本身只是定义为“后入先出”（LIFO）的一种抽象数据结构而已。
（值得一提，甚至我们也可以“数组”是一种抽象数据结构，只要能满足索引和元素的一一对应，都可以叫数组。所以，在有些语言中，数组的底层实现是树！比如PHP，比如Swift：））
当然，对于一个标准库，把栈或者队列看作是抽象数据结构，还是具体数据结构，在具体实现上，是一个设计问题，而不是一个对错问题。
比如在C++中，无论是stack还是queue，都没有设计成接口，都是一个具体的类；
而在Python中，根本就没有设计stack这个类，使用list就可以很好的实现stack功能（虽然没法做访问限制），而使用一个传统的FIFO的queue，则需要实例化一个不是那么传统的deque（双端队列）：）
所以，为什么在Java中，使用一个Queue，需要：Queue q = new LinkedList();
而使用一个Stack，Stack s = new LinkedList(); 这样是错误的？
答案是：Java就是这么设计的。你只能接受它。在Java语言中，Queue是一个接口，而Stack是一个可以直接实例化的类。
===========
所以，现在的问题变成了，为什么Java这么设计？
首先，这里面有历史原因。如果看一下Stack的源码，就会发现，Stack继承Vector，而Vector是一个被现代Java编写近乎弃用的类。Queue的设计整体是更合理的。在Java社区本身也有这样的声音，认为应该把Stack改成和Queue一致的接口。所以，你不是一个人：）
另外一点，更加关键的是，如果抽象有层级的话，Queue的抽象程度也确实比Stack更高！
Stack近乎完全等同于“后进先出的线性数据结构”，而Queue这个词绝不仅仅等于“先进先出的线性数据结构”，这一点在这个课程中，我印象里有过多次强调。Queue更像是一种“有进有出”的数据结构。具体怎么进，怎么出，没关系！有进有出，就能叫Queue！
传统的先进先出队列，是按照时间序定义进出顺序的；
优先队列则是按照优先级定义进出顺序的；
如果你看过我的《看得见的算法》（https://coding.imooc.com/class/138.html ），在里面，介绍迷宫生成问题时，我设计了一个随机队列，则是按照随机的方式定义进出顺序的。
这些都是Queue！甚至，在这个意义下，Stack也是一个Queue，Stack有他自己的进出顺序的规定（后进先出）。
这点，我在我的《看得见的算法》课程中也有强调，并且从这个视角看，我们竟然能统一DFS和BFS两种截然不同的遍历方式——他们本质是一样的，只是用什么Queue不同而已。（这点在《看得见的算法》中有详细介绍，不过扯远了，原谅我做广告：））
所以，Queue本身就是一个比Stack更广义，更抽象的概念。如果他们二者之间一定要选择一个当抽象接口的话，必然是Queue：）
而对于Stack，虽然他也是抽象数据结构，但是它的定义很单一，在具体实现上，使用动态数组实现就很好，没有必要再让用户费心去选择低层的数据结构：）
当然，所有的设计问题，最终解释权都在设计师，而不是第三方。第三方只能解读，而不能解释设计根源。很有可能，最关键的设计根源，就是：我很懒，一开始这么写了，大家也用习惯了，所以就不改了：)
继续加油！：）
932018-11-16
相似问题