limited size; add, remove and shuffle

Question

Adding to the queue would be O(1). So what would be the removing efficiency? I am slightly confused about this. It makes sense for it to be O(1) because we are removing from the head but what if the queue reaches it's max limit of 5 therefore before inserting a new element, the queue would have to dequeue by 1 and move/shuffle the top 4 elements towards the front to insert the new element at the rear (5th position). Would it still be O(1)? Or maybe O(n) because of shuffling method.

I don't need codes or in depth explanation, just a logical explanation would do.

Answer 1

If the queue is implemented as a circular buffer, as, for example the .NET Queue class is, then that's still an O(1) operation, even if you're both adding one item to the end and removing one item from the head. Being a circular buffer it won't need to move all of the items, it simply need to adjust two integer indexes representing where the start/end of the queue is within the buffer.

On top of that, if there's a capacity of 5 then you can say that even if you did need to move all of the items, you are never moving more than 5. Everything is O(1) when n is small. Big O is only relevant when 'n' can scale to large numbers.