我想知道，当我们插入和删除元素时，为什么大O表示法在平均情况下是Array/Stack/Queue的O(1)？
在我的理解中，它是O(1)，因为无论集合中的数据量如何，对元素进行索引和删除都需要恒定的时间，但我仍然有点困惑。任何帮助我消除困惑的人都将不胜感激。
O(1)-表示法意味着操作在恒定时间内执行。
O(n)-表示法表示在线性时间内执行操作，例如遍历列表。
阵列
我们从最明显的一个开始。阵列A具有固定长度n，并且可以通过寻址存储器中的适当位置(即)在恒定时间内访问其元素
A[i]=10;
堆栈
堆栈是后进先出的数据结构。我们总是有一个指向顶部元素的指针/引用。因此，即使堆栈被实现为列表，我们无法在恒定时间内寻址其中的特定元素(我们必须遍历O(n)中的列表)，我们也会使用pop/peak访问最顶层的元素，我们有一个指针/引用，因此可以在恒定时间O(1)。
Stack.pop(); //or peak() perhaps
队列
队列是一种先进先出的数据结构。与堆栈一样，访问队列的特定元素可以在线性时间O(n)中完成，因为我们需要遍历它。但我们通常有一个指向队列第一个和最后一个元素的指针/引用。因此入队和出队都可以在恒定时间内执行O(1)。
对于基于数组的堆栈，所有操作都是O(1)，因为你只能删除堆栈顶部的项(你不必循环、迭代或做任何其他事情)。插入也是一样的。对于基于链接的堆栈，除了析构函数之外，它们也都是O(1)，因为您必须在节点上循环并删除每个节点。对于基于数组的ques，我只确定deque是O(N)，因为你返回了第一个项目，然后你会向前移动。
我建议你看这个家伙的视频，他会深入地解释所有这些。祝你好运