0
我正在研究数据结构，并对堆栈和队列的不同实现中的时间复杂性有所怀疑。实现堆栈和队列操作的时间复杂性
对于队列，是一个元件可以在头部或尾部进行排队，动态数组实现给出O（1）时间摊销用于插入在端部和开头。链表实现给出了O（1）的实现。
对于栈，是一个节点可以在开始时或在列表中，单链表和阵列实施将两者得到O（1）时间复杂度的结束时加入。
我是对的还是我错过了什么？
A
回答
0
如果您维护下一个插入位置的索引，则插入操作将花费恒定的时间量，因此O（1）是正确的。
但是，如果没有索引被维护，那么我们需要搜索插入新元素的正确位置，插入此元素所需的时间会随着数据结构中元素的数量线性增加，因此插入时间这种情况将是O（n）