Queue for two types using 2 queues?

Question

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.

My approach is to use two queues, main and backup

Enqueue

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

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.