educative.io

Dequeuing can be O(1)

Courses
, ,
#1

I was looking into an implementation which uses two pointers, one to the head and one to the tail

If you have a pointer to the tail, then you can insert in the tail with O(1) time and remove from the head with O(1) time (linked list implementation)

You can also do this implementation with an array based queue, but then you have to make the implementation “circular” so you don’t need to shift elements when dequeuing. The queue is full when tail = head

Why do we go for a O(n) implementation here?

#2

Hi @Lucas2,
If you go to the lesson and look at the table, we use an O(1) implementation for enqueuing and dequeuing. Plus, the method used is the one you have explained here in your query.

Regards.