Python - MUST USE STACK! and only allowed O(1) additional space! No recursion.

Question 5 Implement the following function: def permutations (1st) The function is given a list lst of integers, and returns a list containing all the different permutations of the elements in 1st. Each such permutation should be represented as a list. For example, if1st-[1, 2, 3], the call permutations (1st) could return Implementation Requirements: 1. Your implementation should be non-recursive. 2. Your implementation is allowed to use a Stack, a Queue, and (1) additional Hint: Use the stack to store the elements yet to be used to generate the permutations, and use the queue to store the (partial) collection of permutations generated so far