对于实现为:
的Queue，插入操作的性能是什么?(a)一个数组，其中项是无序的
(b)一个数组，其中项按顺序排列
(c)一个链表，项目无序排列。
对于每个操作和每个实现，用Big Oh符号给出性能，并解释足够的算法来证明你的答案。(例如，它需要O(n)次，因为在最坏的情况下....算法会做这样那样的事情....)。
请详细解释一下，这对我很有帮助!
简短的回答:这取决于你的数据结构。
在一个朴素的基于数组的实现(假设固定大小)中，我认为很明显插入是一个常量操作(即，O(1))，假设你没有跑掉数组的末端。这在循环数组中是类似的，具有类似的假设。
动态数组稍微复杂一些。动态数组是固定大小的数组，一旦填充到某一点，就可以将其扩大。因此，对于长度为k时调整大小的动态数组，第一次k-1插入是恒定的(就像插入到普通数组中一样)，第一次k插入需要O(k+1) -将数组内容复制到更大的容器中，然后插入元素的成本。你可以证明这是O(1)插入时间，但这可能超出了你的课程范围。
正如其他人所指出的，排序顺序不会影响标准队列。如果您实际上正在处理一个优先级队列，那么有很多可能的实现，我将让您自己研究。最好的插入时间是0(1)，但这种实现有一些缺点。标准实现是O(log n)插入。
对于链表，插入时间将取决于列表的头部是否是队列的头部(即，无论您是添加到头部还是尾部)。
如果你加上头，那么很容易看出插入是O(1)。如果在尾部添加，那么对于长度为n的列表，也很容易看到插入值为O(n)。要点是，无论选择哪种实现，插入总是O(1)或O(n)中的一个，而删除总是另一个。
然而，有一个简单的技巧可以让您在任何一种情况下都将插入和删除变为0(1)。