堆栈迷思

当我们在讨论堆栈的时候,究竟是在谈论些什么?真的确定我们说的是同一个东西吗?

阅读协议

注意:本文的目的不是让计算机专业出身的你重返大学课堂,再次接受你认为自己已经懂的知识。我当然不可能花时间来重复别人早已说烂的知识,而是带有新发现,以及一些倾向性的观点写下了此文。请自行批判性地阅读。

前提条件:堆栈不是栈!栈不是堆栈!尽管你可能在很多技术博客上、各大技术交流网站上不止一次的看到堆栈一词,很多人用堆栈指代栈,但我还是想说把栈等同于堆栈是十分错误的。甚至术语堆栈就不该存在于世!所以先请读者忘记栈=堆栈这个说法,在完全理解下面的知识后我会说明清楚为什么不要用堆栈这个充满歧义的术语。可以注意到我后面提到的都是”堆和栈“而不是”堆栈“。

内存管理和数据结构下的堆和栈

一个明显的错误是没有理解内存管理的堆和栈以及数据结构的堆和栈,它们之间到底有什么差异和联系。首先需要明确区分内存管理的堆和栈以及数据结构的堆和栈,接下来我会分别用”内存堆“、”内存栈“表明是内存管理的堆和栈,”堆ADT“、”栈ADT“表明是数据结构的堆和栈,以示区别。

内存堆和内存栈是内存分配的一种手段。

内存栈:程序的每个线程都各自有一个栈内存。在线程每次函数调用的时候,会以后进先出(LIFO)的方式预留函数的数据。对栈的操作是操作系统和程序运行时共同决定的,程序代码本身不能控制。

内存堆:程序的每个线程共享一个堆内存。堆内存适用于大量数据的分配。程序动态分配堆,分配和释放都由程序自己决定。

内存栈和内存堆相比较,内存栈分配速度比内存堆要快,所以更适合函数调用的快速分配和释放。但是一旦需要大量内存的时候,需要用堆。当然这不是定理,完全可以根据实际情况采用不同策略。比如python的函数调用完全是在堆上虚拟出来的。

栈ADT:入栈的元素满足后进先出(LIFO)的方式。很简单的定义,没有特殊成分。

在讨论堆ADT前,必须了解一个前提:二叉堆是如此的普遍,以至于经常被称为堆。堆还有其他形式的结构,但是极不常用,各大教材也不爱写。接下来说的堆ADT就是特指二叉堆。

堆ADT:堆的结构是二叉树的一种,并且满足父结点比它的两个子结点都要大(或都小)的条件。这种结构可以实现优先队列(priority queue)。

优先队列(priority queue):每个元素除其自身,都额外附带一个优先级;按最高优先级弹出元素。堆的结构性质正好可以用来实现优先队列。具体的操作步骤可以参考任何一本数据结构的教科书。通常你会看到”堆(优先队列)“的提法,但是要清楚堆只是优先队列的一种高效实现方法,当然优先队列还有其他实现方法,因为优先队列的定义是如此的简单。

注意:堆不是FIFO的数据结构!如果看到有任何人提到堆是FIFO的,请当即驳斥。堆实现了优先队列,但我们从优先队列的定义中可以知道,优先队列可不是FIFO。一般来说,队列(queue)才是FIFO的。所以,真正与栈ADT相对的概念是队列。这里存在一个小小的陷阱:双端队列(deque),优先队列不是FIFO的结构,尽管它们带有后缀”队列“。请不要将这几个队列归为一谈。

重点来了

说这么多,内存堆和数据结构堆到底有什么联系啊?三个字,没联系。一句话,它们同时都叫作堆,但是完全不同,重名只是一个巧合。内存堆也不是用数据结构堆实现的,更详细的理由是我在stackoverflow中找到的:Why are two different concepts both called “heap”?(为什么两个不同的概念都被称为”堆“?) 以下是最高票答案的粗略翻译:

Donald Knuth在《计算机程序设计艺术》中说道:
从1975开始有几位作者把可获取的内存池称为”堆”。
他没有表明是哪几位作者,也没有引用什么论文,而是说“堆”是优先队列的传统表达。

究其根本,是意外,是历史原因,才导致内存堆和数据结构堆的重名。实际上该答案下面的评论也谈到,把内存堆称为“池(pool)”是更好的表达。毕竟堆这个词只是想表达杂乱的摆放,概念更接近计算机术语中的池。

那么内存栈和数据结构栈呢?内存栈的确是以LIFO的方式在扩展和释放,所以才会说内存栈是用数据结构中的栈实现的。

大混乱

正因为如此,我才会极力阻止栈=堆栈的危险想法。想必你在看这篇文章之前看到过下列说法:

栈(stack)又名堆栈,它是一种运算受限的线性表。

节选自百度百科词条 – 栈(计算机术语)第一句,2018年11月12日

以及:

堆栈(英语:stack)又称为栈或堆叠,是计算机科学中一种特殊的串列形式的抽象数据类型

节选自中文维基百科词条 – 堆栈 第一句,2018年11月12日

实际上英语表达中不存在栈又名堆栈的说法,这种说法你永远只能在中文的文章中看到。我很怀疑中国的IT圈是完全封闭的,以至于创造性地发明了术语“堆栈”。谁来告诉我,stack翻译成栈,“堆”字是哪里蹦出来的?为什么大家又要把stack叫成堆栈啊?

堆栈应该只在内存管理概念里出现。在英语表达里,通常用“heap and stack”并称内存管理的堆和栈,并不会直接称其为“heap stack”。如果是想把heap and stack翻译为堆栈,那么堆栈是不可能理解为栈的。我看到“堆栈”混同于“栈”只在中文技术圈中出现。这不是一个好习惯。严重的说,“堆栈”一词误导数据结构的初学者。经常有人无法区分内存的堆栈和数据结构的堆和栈。堆和栈在数据结构领域完全是不相干的概念,为什么活生生混为一谈呢?我曾在网上浏览初学者分享的笔记,看到有的初学者认为堆和栈是相对的概念,甚至认为既然栈是LIFO的,那么堆就是FIFO的。这种类型的错误数不胜数,比如在百度百科中的词条堆栈中就可以找到这种说法(里面的错误多的离谱)。在数据结构中,堆和栈并没有任何并列讨论的价值。所以当我们在讨论数据结构的时候,请停止使用“堆栈”一词。我建议你将堆栈从大脑中完全删除。

一点点思考

其实术语混乱的现象还挺多的,在许多领域中都会出现。稍不注意,即被迷惑。譬如双端队列的单词为deque,但有些人又把它叫做dequeue。似乎可行,但是这却和queue的出队操作(dequeue)产生命名冲突。所以需要我们在实际学习中多动动脑子,不要轻易被结论所误导,不能把书上教程上的某一句话奉为皋臬。结论极有可能是错的,但却会对接下来的学习造成毁灭性的打击,而且一旦固化将很难逆转。

参考文献

什么是堆和栈,它们在哪儿?

基础性的知识,他写得比我好!

发表评论

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