Big Oh question ...

[mattg1981]

Hey yall .. I was wondering what the general runtime is for stacks and queues ....

I believe they are O(1) ... which means constant. Am I correct, generally speaking?

 

[CTho9305]

A stack, yes. A queue could be implemented in an O(n) manner (if you used a linked list and had to search to the end), but I think a smart implementation (ring buffer, although the size would then be finite) would be O(1).

 

[kamper]

If you're using a linked list you shouldn't be searching to the end, you should have a reference to both the head and tail of the queue

The general push/pop and enqueue/dequeue ops should all be O(1) if you implement properly but there are other operations that take longer. If you're queue is a priority queue insertion can take from log(n) up to n, depending on implementation. If you want to allow random access to the insides of the structures then you're also looking at higher times. A java Stack, for instance, extends the Vector and so allows all kinds of itemAt() and insertAt() functionality.

 

[mattg1981]

thanks guys