You are given a Stack of people. They should be paired off as man with woman, woman with

man. If a male and a female are consecutive in the stack, they get paired immediately. If there

are consecutive females found without any subsequent males, then the spare females should

be saved in a Queue for future pairing. If there are consecutive males found without any

subsequent females, we try to pair a male with the first spare female $[$if available$]$ from the

Queue. If no spare female is available, then the male is discarded. The same logic applies to

consecutive females without any subsequent males.

The stack class and the Queue class are implemented for you. The public instance

methods in the Stack class are push$(),$ pop$(),$ peek$(),$ and isEmpty$().$ The public

instance methods in the Queue class are enq$(),$ deq$(),$ peek$(),$ and isEmpty$().$ In

both classes, isEmpty$()$ returns a boolean value, peek$()$ and pop$()$ returns None for

underflow. All other members of both classes are private. You can only use the public

instance methods. No need to consider the overflow exception for both Stack and Queue

classes.

Your task is to complete the given method dance$\_$pair$()$ that takes a stack and prints

every male$-$female pair.

Every male and female are written in this way $-$ M$\_$id or F$\_$id$.$ A method called

id$\_$gender$\_$extractor$($s$)$ is implemented for you that returns the id and gender from a

string, s $.$

You cannot use any data structure other than stack and queue. please follow the picture of the question

Given: