I'm reading the book Cracking the Code.

The answer for this question suggests a solution using timestamps and two separate queues. This is straightforward and involves simply enqueuing into the appropriate queues. Dequeuing oldest involves checking timestamps of front of both queues and removing the oldest.

I'm wondering if there is a way to do this without using an additional timestamp field.

enter image description here

My approach is to use two queues, main and backup


I simply push into backup

Dequeue Dog/Cat aka. specific type dequeue

I check if front of main has this type. If not or if main is empty, then I go to backup.

If backup contains the right type, dequeue it

If backup does not contain it, then shift from backup to main i.e. dequeue from backup and enqueue to main

Dequeue oldest pet

dequeue from main if main has elements

If main is empty, dequeue from backup

  • 1
    $\begingroup$ I think you are over-complicating it... You just need a dogs queue and a cats queue, its that simple. $\endgroup$
    – nir shahar
    Commented Dec 26, 2021 at 10:08
  • $\begingroup$ the whole point of posting this question is to discuss an alternate approach... $\endgroup$ Commented Dec 26, 2021 at 17:33
  • 1
    $\begingroup$ However your idea also uses two queues. I don't understand what you want to ask here then. $\endgroup$
    – nir shahar
    Commented Dec 26, 2021 at 21:56
  • $\begingroup$ "I'm wondering if there is a way to do this without using an additional timestamp field." $\endgroup$ Commented Dec 27, 2021 at 2:02
  • 1
    $\begingroup$ Do you allow to use more than $2$ queues? Or maybe a modified version of a queue? $\endgroup$
    – nir shahar
    Commented Dec 27, 2021 at 12:26

1 Answer 1


Your solution seems to have higher time complexity than needed. If you have $n$ dogs and then $n$ cats then dequeuing all cats will cost you $O(n^2)$ as you need to go through dogs first.

I'd go with three queues: all animals, dogs, cats.

Enqueue: Create an instance of dog/cat, push into all animals queue. Next, push the same instance to the dog/cat queue appropriately.

Dequeue Dog/Cat: just dequeue from dog/cat queue. Do not touch all animals queue.

Dequeue oldest: dequeue from all animals queue. If it's a dog then peek a dog from the dog queue. If those are the same instances - dequeue from dog queue and return. Otherwise discard the dog from the all animals queue and repeat.

Time complexity: each animal is inserted exactly once to each queue and removed exactly once so amortized time is $O(1)$ for enqueue and $O(1)$ for dequeue.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.