数组&链表&堆栈&队列

数组：顺序存储【连续地址存储】

查找：通过index直接定位 --> O(1)

插入分为以下两种情况：

• 插到末尾 --> O(1)
• 查到中间需要移动添加元素后面的所有元素位置, 再添加元素 --> O(n)

删除分为以下两种情况：

• 删除末尾元素：删除末尾不需要考虑移动元素位置 --> O(1)

• 删除中间需要移动删除元素后面的所有元素位置, 再删除元素 --> O(n)

链表：链式存储【非连续地址储存】

【链式存储】(next --> 指针链向下一个节点)

• 查找：O(n)
• 插入： O(1)

栈(stack)又称【堆栈】

• 后入先出 - Last In First Out(LIFO)【eg：在桌面上堆盘子，只能从栈顶取】

• 栈是只能在一端栈顶top进行插入与删除。另一端是栈底bottom。当表中没有元素时称空栈。

• 栈具有记忆作用，程序设计中的函数调用、递归调用等都是通过栈实现的【递归调用导致的栈溢出】

队列(queue)

• 先进先出 - First In First Out(FIFO)【eg：生活中的排队，只能从栈顶取】

• 队列只能在表的一端(队头)进行删除操作、在另一端(队尾)进行删除操作

注意别混淆

数据结构与内存管理中的堆和栈的区别

• 数据结构 中的stack我们叫做栈(堆栈)，其实是两种不同的数据结构，即堆和栈，堆实质上是满足一定性质的完全二叉树，而栈是“后进先出”的一种线性数据结构，它们与队列queue数据结构相对，queue是先进先出的线性数据结构，它们都是数据结构中的概念

• 内存管理 中的堆栈，其实应该分为“堆heap”和“栈stack”两个部分，在内存管理中发挥不同的作用。以js数据类型为例，基本数据类型的存储在栈区中，而引用类型的值则存储在堆区中