Why Stack and Queue have insertion operation O(1)?

As was said in lectures, both Stack and Queue have insertion operation complexity O(1), BUT both of them have resize() function call if there is no free place left for new elements, so overall complexity should be O(n). So why it is used to said, that insertion operation complexity O(1), when if actually O(N)? Thanks.

Hi, Iâ€™m just starting the course, so apologies if Iâ€™m ahead of myself to offer an answer here. I think you ask a great question, especially where big O is supposed to model the worst case scenario.

In the SE 8 docs, the Queue interface add method inserts only if without â€śimmediately violating capacity restrictions, returning `true` upon success and throwing an `IllegalStateException` if no space is currently available.â€ť

Stacks derive from the List interface: thereâ€™s an implementation of the List interface add method which accepts an index at which to insert the element, throwing an `IndexOutOfBoundsException` .

Itâ€™s possible iâ€™m off-base here, but hopefully thereâ€™s something useful in this response

2 Likes

Hello,

1 Like

Queue is linear data structure which work in first in first out way. It is one of the applications of array, so we operate the queue from only one end for the insertion and deletion. When you perform the insert or delete operation on queue only one element is operated (i.e. either rear++ or front++). The time complexity of insert or delete element in/from queue is O (1).

Similarly, Stack is linear data structure which work in Last in first out way. we operate the stack only from one end means insertion and deletion take place from the same end . When you perform the insert or delete operation on stack only one element is operated (i.e. either top++ or topâ€“). The time complexity of insert or delete element in/from stack is O (1).

Neither of these data structures have to be implemented using an array. If you implement these data structures using linked lists you can certainly get constant-time insertion.

NOTE: `Queue` is just an interface in Java and does not imply any particular implementation. One implementation is `ArrayDeque` which is backed by an array, but another implementation is `LinkedList` which is backed by a doubly-linked list. The `LinkedList` implementation of `Queue` does not have any need to resize as new elements are added, but the `ArrayDeque` does. The Javadoc for `Queue` is trying to be generic to cover both cases which is why it says â€śif it is possible to do so immediately without violating capacity restrictionsâ€ť (because it cannot guarantee that all implementations do not have capacity restrictions).

Also, it is pretty common to talk about â€śamortized constant timeâ€ť (or more generally â€śamortizedâ€ť time complexity). When we do, we are saying that the time complexity can basically be considered O(1) for practical purposes. This is because it would be misleading to call the insertion time complexity for an array-backed queue to be O(N) since the vast majority of your insertion operations would be constant time (especially if you chose a good initial size). In fact, that is precisely what the `ArrayDeque` Javadocs say:

Most `ArrayDeque` operations run in amortized constant time.