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

Data Structures
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.

2

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.”
https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html#add-E-

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 .
https://docs.oracle.com/javase/8/docs/api/java/util/List.html#add-int-E-

It’s possible i’m off-base here, but hopefully there’s something useful in this response :+1:

2 Likes
3

Hello,
actually, your answer explain a lot, so thank you very much for reply :slight_smile:

1 Like
4

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).

5

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.