我想知道为什么我们应该使用堆栈,因为数组或链表可以做堆栈可以做的所有事情?为什么我们要把它单独命名为“数据结构”呢?在现实世界中,只需使用数组就足以解决问题;为什么要费心去实现一个限制自己只能从集合顶部推送和弹出的堆栈?
最佳答案
我认为最好使用术语“数据类型”来指代其行为由某些接口(interface)、代数或操作集合定义的事物。诸如此类的事情
- 堆栈
- 队列
- 优先队列
- 出列
- 列出
- 套
- 层次结构
- map (词典)
是类型,因为对于每个类型,我们只列出他们的行为。栈之所以是栈,是因为它们只能被压入和弹出。队列之所以是队列,是因为……(你明白了)。
另一方面,数据结构是通过其组件排列方式定义的数据类型的实现。示例包括
- 数组(通过索引进行恒定时间访问)
- 链接列表
- 位图
- BST
- 红黑树
- (a,b)-树(例如 2-3 棵树)
- 跳过列表
- 哈希表(许多变体)
- 邻接矩阵
- 布隆过滤器
- 朱迪数组
- 尝试
很多人确实混淆了数据结构和数据类型这两个术语,但最好不要太迂腐。堆栈是数据类型,而不是数据结构,但同样,为什么要太迂腐。
为了回答您的具体问题,在我们希望确保仅通过压入和弹出来修改数据的情况下,我们使用堆栈作为数据类型,并且我们从不违反此访问模式(即使是意外)。
在底层,我们可以使用链表作为堆栈的实现。但大多数编程语言都会提供一种方法来限制接口(interface),以允许我们的代码以后进先出的方式可读且安全地使用我们的数据。
TL;DR:可读性。安全性。
关于arrays - 为什么我们应该使用堆栈,因为数组或链表可以完成堆栈可以执行的所有操作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26541707/