# Queue for two types using 2 queues?

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

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

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.
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.