Implement a Queue using 2 stacks s1 and s2 .
A Query Q is of 2 Types
(i) 1 x (a query of this type means  pushing 'x' into the queue)
(ii) 2   (a query of this type means to pop element from queue and print the poped element)
Note :- If there is no element return -1 as answer while popping.
Example 1:
Input:
5
1 2 1 3 2 1 4 2
Output: 
2 3
Explanation: 
In the first testcase
1 2 the queue will be {2}
1 3 the queue will be {2 3}
2   poped element will be 2 the queue 
    will be {3}
1 4 the queue will be {3 4}
2   poped element will be 3.
Example 2:
Input:
4
1 2 2 2 1 4
Output: 
2 -1
Explanation: 
In the second testcase 
1 2 the queue will be {2}
2   poped element will be 2 and 
    then the queue will be empty
2   the queue is empty and hence -1
1 4 the queue will be {4}.
Your Task:
You are required to complete the two methods push which take one argument an integer 'x' to be pushed into the queue and pop which returns a integer poped out from other queue(-1 if the queue is empty). The printing is done automatically by the driver code.
Expected Time Complexity : O(1) for push() and O(N) for pop() or O(N) for push() and O(1) for pop()  
Expected Auxilliary Space : O(1).
Constraints:
1 <= Q <= 100
1 <= x <= 100
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



#Function to push an element in queue by using 2 stacks.

def Push(x,stack1,stack2):

    '''

    x: value to push

    stack1: list

    stack2: list

    '''

    #code here



#Function to pop an element from queue by using 2 stacks.

def Pop(stack1,stack2):

    

    '''

    stack1: list

    stack2: list

    '''

    #code here

Solutions:
def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if len(stack1) == 0:
		return -1
	n = len(stack1)
	for i in range(n):
		stack2.append(stack1.pop())
	ans = stack2.pop()
	m = len(stack2)
	for i in range(m):
		stack1.append(stack2.pop())
	return ans


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if len(stack1) == 0:
		return -1
	while len(stack1) != 0:
		num = stack1.pop()
		stack2.append(num)
	item = stack2.pop()
	while len(stack2) != 0:
		num = stack2.pop()
		stack1.append(num)
	return item


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if stack1 == []:
		return -1
	while stack1 != []:
		val = stack1.pop()
		stack2.append(val)
	ans = stack2.pop()
	while stack2 != []:
		val = stack2.pop()
		stack1.append(val)
	return ans


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if len(stack1) == 0 and len(stack2) == 0:
		return -1
	if len(stack2) == 0:
		while len(stack1) != 0:
			stack2.append(stack1.pop())
	return stack2.pop()


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if stack2:
		return stack2.pop()
	while stack1:
		a = stack1.pop()
		stack2.append(a)
	while stack2:
		return stack2.pop()
	return -1


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if len(stack1) != 0:
		return stack1.pop(0)
	else:
		return -1


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if not stack1 and (not stack2):
		return -1
	if not stack2:
		while stack1:
			stack2.append(stack1.pop())
	return stack2.pop()


def Push(x, s1, s2):
	s1.append(x)

def Pop(s1, s2):
	if s2:
		return s2.pop()
	while s1:
		a = s1.pop()
		s2.append(a)
	while s2:
		return s2.pop()
	return -1


def Push(x, s1, s2):
	s1.append(x)

def Pop(s1, s2):
	if not s2:
		if not s1:
			return -1
		while s1:
			r = s1.pop()
			s2.append(r)
		k = s2.pop()
		while s2:
			l = s2.pop()
			s1.append(l)
		return k
	return -1


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if len(stack1) == 0 and len(stack2) == 0:
		return -1
	elif len(stack2) == 0 and len(stack1) > 0:
		while len(stack1):
			temp = stack1.pop()
			stack2.append(temp)
		return stack2.pop()
	else:
		return stack2.pop()


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(s1, s2):
	if not stack2:
		while stack1:
			stack2.append(stack1.pop())
	if not stack2:
		return -1
	return stack2.pop()


def Push(x, s1, s2):
	while len(s1) != 0:
		s2.append(s1[-1])
		s1.pop()
	s1.append(x)
	while len(s2) != 0:
		s1.append(s2[-1])
		s2.pop()

def Pop(s1, s2):
	if len(s1) == 0:
		return -1
	x = s1[-1]
	s1.pop()
	return x


def Push(x, stack1, stack2):
	stack1.insert(0, x)
	stack2.insert(0, x)

def Pop(stack1, stack2):
	if stack1 == []:
		return -1
	return stack1.pop()
	return stack2.pop()


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if not stack1:
		return -1
	for i in range(len(stack1) // 2):
		(stack1[i], stack1[len(stack1) - 1 - i]) = (stack1[len(stack1) - 1 - i], stack1[i])
	k = stack1.pop()
	for i in range(len(stack1) // 2):
		(stack1[i], stack1[len(stack1) - 1 - i]) = (stack1[len(stack1) - 1 - i], stack1[i])
	return k


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if stack2:
		res = stack2.pop()
		return res
	while stack1:
		i = stack1.pop()
		stack2.append(i)
	if stack2:
		res = stack2.pop()
		return res
	return -1


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if len(stack1) == 0:
		return -1
	for i in range(len(stack1) - 1):
		stack2.append(stack1.pop())
	j = stack1.pop()
	for i in range(len(stack2)):
		stack1.append(stack2.pop())
	return j


def Push(x, stack1, stack2):
	if len(stack1) > 0:
		stack1.append(x)
	elif len(stack2) > 0:
		stack2.append(x)
	else:
		stack1.append(x)

def Pop(stack1, stack2):
	if len(stack1) > 0:
		giving_stack = stack1
		receiving_stack = stack2
	else:
		giving_stack = stack2
		receiving_stack = stack1
	if len(giving_stack) == 0:
		return -1
	while len(giving_stack) > 1:
		receiving_stack.append(giving_stack.pop(-1))
	res = giving_stack.pop(-1)
	while len(receiving_stack) > 0:
		giving_stack.append(receiving_stack.pop(-1))
	return res


def Push(x, first, second):
	first.append(x)

def Pop(first, second):
	if len(second):
		return second.pop()
	else:
		y = len(first)
		if y == 0:
			return -1
		while y != 0:
			second.append(first.pop())
			y -= 1
		return second.pop()


def Push(x, stack1, stack2):
	stack1.append(x)

def Pop(stack1, stack2):
	if stack2 == []:
		while stack1:
			stack2.append(stack1.pop())
		if stack2:
			op = stack2.pop()
		else:
			op = -1
	elif stack2:
		op = stack2.pop()
	else:
		op = -1
	return op