数据结构能否由另一种数据结构实现？基于Array、Stack、Queue的相关疑问

你的理解没有偏差，数据结构完全可以基于其他数据结构构建，这是计算机科学领域非常普遍的实践。

核心要区分两个概念：数据结构的「抽象定义」和「底层实现」：

• 抽象定义只规定数据结构的行为规则、对外暴露的操作、数据访问逻辑，和底层实现方式无关：
  • 数组的抽象定义是支持通过索引随机访问任意位置的元素
  • 栈的抽象定义是仅允许在单端进行元素增删操作，符合LIFO（后进先出）规则
  • 队列的抽象定义是支持在一端新增、另一端删除元素，符合FIFO（先进先出）规则
• 底层实现只需要满足上层抽象定义的规则即可，没有强制要求必须用什么底层结构。

常见的实现案例包括：

• 栈和队列既可以用数组实现，也可以用链表实现，只要最终对外暴露的操作符合对应的存取规则，使用者完全不需要感知底层的实现逻辑
• 大多数编程语言的标准库哈希表，都是基于「数组 + 链表/红黑树」的组合实现，用来解决哈希冲突问题
• 常用的优先队列大多基于堆实现，而堆本身又经常基于数组来实现
• 跳表、字典树等更复杂的数据结构，也都是基于数组、链表这类基础数据结构封装规则实现的

你提到的数组和栈、队列的组织逻辑不同，只是二者在抽象定义层面的差异，完全不影响后者基于前者实现。很多高级语言内置的数组已经自带了push、pop、shift、unshift等方法，直接用来封装栈、队列几乎不需要额外的逻辑开发，是成本很低的实现方案。

内容的提问来源于stack exchange，提问作者Ivan