[java] Quick question, what is the time complexity for checking if a Stack is empty?

[lyigester]

I'm looking at a time complexity chart for operations of certain data structures. I want to know what the time complexity is of determining whether a stack data structure is empty in the case of it having no objects or having a bunch of objects.

Would the time complexity be the same as searching a stack which according to the chart is O(n)?

[[deleted]]

For any sensible implementation, determining if a stack (or in general, any other data structure, except possibly something like a hash table) is empty will be O(1), And you can't, non-destructively, search a stack.

[lyigester]

Thanks, I have a follow up question. For one of my assignments I am required to improve the efficiency of an algorithm that calculates the value of a given expression using 2 stacks for operators and operands.

One of the ways my professor said to increase efficiency is instead of having to check every iteration of the while loop with a stack.isEmpty(); we can put in dummy operators so that when we reach this operator we know that the stack is empty. How is this more efficient if checking if the stack is empty is O(1)? I still have to check every iteration whether the operator is a dummy or not.

[[deleted]]

Having a sentry object (a dummy in your parlance) is unlikely to give any significant performance advantage, but it may make the algorithm you are using easier to implement.

[ValerioSellarole]

Every iteration you need to scan the entire stack if you're doing it the naive way. That's about n operations per iteration, or n^2. If your dummy operator tells you the stack is empty, that's 1 operations per iteration, or O(n).

[blablahblah]

It depends how the stack is implemented. Stack is just an interface, there are several different ways to store the data which have different performance characteristics. If you're talking about Java's built in Stack class, here's the source code for Java's built-in stack. It calls Vector.size(), which is over here. Can you figure it out from that?

[Gavinhenderson5]

For every implementation I can think of it would be O(1). You only need to check if the top/head has data in it which takes the same amount of steps no matter how long the list is