栈（Stack）和队列（Queue）是否属于LinkedList？索引时间复杂度是否一致？

1. 栈和队列是否属于LinkedList的范畴？ #

首先要明确概念边界：

• 栈、队列是逻辑数据结构，仅定义元素的进出规则：栈遵循后进先出（LIFO），仅允许在同一端做增删；队列遵循先进先出（FIFO），仅允许一端增、另一端删。
• LinkedList是物理存储结构，属于链式存储的具体实现，只是可以用来实现栈和队列的可选底层方案之一，二者本身不属于LinkedList的范畴。除了LinkedList之外，数组、动态数组等其他存储结构也都可以实现栈和队列。

举个常见的语言实现例子：Java标准库中Stack类是基于数组实现的，可同时作为栈、队列使用的ArrayDeque类也是基于数组实现的，只有明确基于LinkedList封装的栈/队列才用到了链式存储结构。

2. 「栈和队列的索引时间复杂度和LinkedList一样为O(n)」的假设是否成立？ #

该假设不成立，需要分场景判断：

• 如果用LinkedList作为底层实现栈/队列：首先栈和队列的标准操作本身就不包含随机索引操作，常规的入栈/出栈、入队/出队、查看栈顶/队首元素操作，只要LinkedList维护了头尾指针，时间复杂度都是O(1)。如果硬要对这种实现的栈/队列做随机索引（比如查找第k个元素），时间复杂度才会和直接操作LinkedList一致为O(n)。
• 如果用数组/动态数组作为底层实现栈/队列：本身数组随机索引的时间复杂度是O(1)，此时对栈/队列做随机索引的时间复杂度也为O(1)，和LinkedList的O(n)完全不同。

本质上随机索引不是栈和队列的设计目标操作，实际开发中几乎不会对标准栈/队列做随机索引访问。

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