Implement a Queue using Linked List. 
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 an element from the queue and print the poped element)
Example 1:
Input:
Q = 5
Queries = 1 2 1 3 2 1 4 2
Output: 2 3
Explanation: n 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:
Q = 4
Queries = 1 2 2 2 1 3 
Output: 2 -1
Explanation: In the second testcase 
1 2 the queue will be {2}
2   poped element will be {2} then
    the queue will be empty. 
2   the queue is empty and hence -1
1 3 the queue will be {3}.
Your Task:
Complete the function push() which takes an integer as input parameter and pop() which will remove and return an element(-1 if queue is empty).
Expected Time Complexity: O(1).
Expected Auxiliary Space: O(1).
Constraints:
1 <= Q <= 100
1 <= x <= 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: # A linked list (LL) node 

# to store a queue entry 

'''class Node: 

      

    def __init__(self, data): 

        self.data = data 

        self.next = None'''

        

class MyQueue:

    

    #Function to push an element into the queue.

    def push(self, item): 

         

         #Add code here

    

    #Function to pop front element from the queue.

    def pop(self):

         

         #add code here

Solutions:
class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.front = None
		self.rear = None

	def push(self, item):
		node = Node(item)
		if self.front is None:
			self.front = self.rear = node
		else:
			self.rear.next = node
			self.rear = node

	def pop(self):
		if self.front is None:
			return -1
		value = self.front.data
		if self.front == self.rear:
			self.front = self.rear = None
		else:
			self.front = self.front.next
		return value


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.tail = None

	def push(self, item):
		node = Node(item)
		if self.head == None:
			self.head = node
			self.tail = node
		else:
			self.tail.next = node
			self.tail = node

	def pop(self):
		if self.head == None:
			return -1
		else:
			temp = self.head
			if self.head == self.tail:
				self.head = None
				self.tail = None
			else:
				self.head = self.head.next
			return temp.data


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.temp = None

	def push(self, item):
		newNode = Node(item)
		if self.temp is None or self.head is None:
			self.temp = self.head = newNode
		else:
			self.temp.next = newNode
			self.temp = self.temp.next

	def pop(self):
		if self.head is None:
			return -1
		ret = self.head.data
		self.head = self.head.next
		return ret


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = self.tail = None

	def push(self, data):
		node = Node(data)
		if not self.head:
			self.head = self.tail = node
		else:
			self.tail.next = node
			self.tail = self.tail.next

	def pop(self):
		if not self.head:
			self.tail = None
			return -1
		value = self.head.data
		self.head = self.head.next
		return value


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.front = None
		self.rear = None

	def isEmpty(self):
		return self.front == None

	def push(self, item):
		linkedListItem = Node(item)
		if self.rear == None:
			self.rear = self.front = linkedListItem
		else:
			self.rear.next = linkedListItem
			self.rear = linkedListItem

	def pop(self):
		if self.isEmpty():
			return -1
		elif self.rear == self.front:
			temp = self.front
			self.rear = self.front = None
			return temp.data
		else:
			temp = self.front
			self.front = temp.next
			return temp.data


class MyQueue:

	def __init__(self):
		self.queue = []

	def push(self, x: int) -> None:
		self.queue.append(x)

	def pop(self) -> int:
		if not self.queue:
			return -1
		return self.queue.pop(0)


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.tail = None

	def push(self, item):
		node = Node(item)
		if self.head == None:
			self.head = node
			self.tail = node
		self.tail.next = node
		self.tail = node

	def pop(self):
		if self.head == None:
			return -1
		elif self.head == self.tail:
			kevin = self.head.data
			self.head = None
			self.tail = None
			return kevin
		kevin = self.head.data
		self.head = self.head.next
		return kevin


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.rear = None
		self.front = None

	def push(self, item):
		temp = Node(item)
		if self.rear == None:
			self.front = temp
		else:
			self.rear.next = temp
		self.rear = temp

	def pop(self):
		if self.front == None:
			return -1
		else:
			res = self.front.data
			self.front = self.front.next
			if self.front == None:
				self.rear = None
		return res


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = Node(0)
		self.curr = self.head

	def push(self, item):
		node = Node(item)
		self.curr.next = node
		self.curr = node

	def pop(self):
		res = -1
		if self.head.next is not None:
			node = self.head.next
			res = node.data
			self.head.next = self.head.next.next
			del node
			if self.head.next is None:
				self.curr = self.head
		return res


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.front = self.rear = None

	def isEmpty(self):
		return self.front == None

	def push(self, item):
		temp = Node(item)
		if self.rear == None:
			self.front = self.rear = temp
			return
		self.rear.next = temp
		self.rear = temp

	def pop(self):
		if self.isEmpty():
			return -1
		temp = self.front
		self.front = temp.next
		if self.front == None:
			self.rear = None
		return str(temp.data)


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.tail = None

	def push(self, item):
		item_node = Node(item)
		if self.head is None or self.tail is None:
			self.head = item_node
			self.tail = item_node
		else:
			self.tail.next = item_node
			self.tail = self.tail.next

	def pop(self):
		if self.head is None:
			return -1
		item = self.head.data
		self.head = self.head.next
		return item


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.node = None
		self.head = None

	def push(self, item):
		if self.head is None:
			self.node = Node(item)
			self.head = self.node
		else:
			self.node.next = Node(item)
			self.node = self.node.next

	def pop(self):
		if self.head is None:
			return -1
		else:
			x = self.head
			self.head = self.head.next
			x.next = None
			return x.data


class Node:

	def __init__(self, data):
		self.next = None
		self.data = data
		self.prev = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.rear = None

	def push(self, el):
		box = Node(el)
		if self.head is None:
			self.head = box
			self.rear = box
			return
		self.head.prev = box
		box.next = self.head
		self.head = box

	def pop(self):
		if self.rear is None:
			return -1
		elif self.rear.prev is None:
			el = self.rear.data
			self.rear = self.head = None
			return el
		el = self.rear.data
		prev = self.rear.prev
		self.rear.prev = None
		self.rear = prev
		self.rear.next = None
		return el


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None

	def push(self, item):
		new_node = Node(item)
		if self.head is None:
			self.head = new_node
		else:
			n = self.head
			while n.next is not None:
				n = n.next
			n.next = new_node

	def pop(self):
		if self.head is None:
			return -1
		else:
			x = self.head.data
			self.head = self.head.next
			return x


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.front = None
		self.rear = None

	def isEmpty(self):
		return not self.front and (not self.rear)

	def push(self, data):
		temp = Node(data)
		if self.isEmpty():
			self.front = self.rear = temp
			return
		self.rear.next = temp
		self.rear = temp

	def pop(self):
		if self.isEmpty():
			return -1
		res = self.front.data
		self.front = self.front.next
		if not self.front:
			self.rear = None
		return res


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.last = None

	def push(self, item):
		node = Node(item)
		if self.head == None:
			self.head = node
			self.last = self.head
		else:
			self.last.next = node
			self.last = node

	def pop(self):
		if self.head == None:
			return -1
		else:
			res = self.head.data
			self.head = self.head.next
			return res


class MyQueue:

	def __init__(self):
		self.d = []

	def push(self, item):
		self.d.append(item)
		return self.d

	def pop(self):
		if len(self.d) == 0:
			return -1
		return self.d.pop(0)


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = self.tail = None

	def push(self, item):
		newNode = Node(item)
		if not self.head:
			self.head = self.tail = newNode
			return
		self.tail.next = newNode
		self.tail = newNode

	def pop(self):
		if not self.head:
			return -1
		val = self.head.data
		self.head = self.head.next
		if not self.head:
			self.tail = None
		return val


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.start = None
		self.end = None

	def push(self, item):
		newNode = Node(item)
		if not self.start:
			self.start = newNode
			self.end = newNode
		else:
			self.end.next = newNode
			self.end = newNode

	def pop(self):
		if not self.start:
			return -1
		val = self.start.data
		if self.start == self.end:
			self.start = None
			self.end = None
		else:
			self.start = self.start.next
		return val


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None

	def push(self, item):
		newNode = Node(item)
		if not self.head:
			self.head = newNode
			return self.head
		curr = self.head
		while curr.next:
			curr = curr.next
		curr.next = newNode

	def pop(self):
		if not self.head:
			return -1
		popEle = self.head
		self.head = self.head.next
		return popEle.data


class MyQueue:

	def __init__(self):
		self.head = None

	class Node:

		def __init__(self, data):
			self.data = data
			self.next = None

	def push(self, item):
		if self.head == None:
			self.head = self.Node(item)
		else:
			node = self.Node(item)
			h = self.head
			while h.next:
				h = h.next
			h.next = node

	def pop(self):
		if self.head:
			h = self.head
			self.head = self.head.next
			h.next = None
			return h.data
		else:
			return -1


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.tail = None

	def push(self, item):
		if self.head == None:
			self.head = Node(item)
			self.tail = self.head
		else:
			self.tail.next = Node(item)
			self.tail = self.tail.next

	def pop(self):
		if self.head == None:
			return -1
		if self.head == self.tail:
			first = self.head.data
			self.head = None
			self.tail = None
			return first
		else:
			top = self.head.data
			self.head = self.head.next
			return top


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.tail = None
		self.count = 0

	def push(self, item):
		newNode = Node(item)
		if self.head is None:
			self.head = newNode
			self.tail = newNode
		else:
			self.tail.next = newNode
			self.tail = newNode
		self.count += 1

	def pop(self):
		if self.head == None:
			return -1
		else:
			data = self.head.data
			self.head = self.head.next
			self.count -= 1
			if self.head == None:
				self.tail = None
		return data


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.front = self.tail = None

	def push(self, item):
		temp = Node(item)
		if self.front == None and self.tail == None:
			self.front = self.tail = temp
		self.tail.next = temp
		self.tail = temp

	def pop(self):
		if self.front == None:
			return -1
		elm = self.front.data
		if self.front == self.tail:
			self.front = self.tail = None
		else:
			temp = self.front
			self.front = temp.next
			elm = temp.data
		return elm


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = Node(-1)
		self.curr = self.head
		self.c = 0

	def push(self, item):
		self.curr.next = Node(item)
		self.curr = self.curr.next
		self.c += 1

	def pop(self):
		temp = self.head.next
		if temp == None:
			return -1
		self.head.next = temp.next
		self.c -= 1
		if self.c == 0:
			self.curr = self.head
		return temp.data


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.front = None
		self.rear = None
		self.size = 0

	def isEmpty(self):
		return self.size == 0

	def push(self, item):
		node = Node(item)
		if self.rear == None:
			self.front = node
		else:
			self.rear.next = node
		self.rear = node

	def pop(self):
		if self.front == None:
			return -1
		else:
			res = self.front.data
			self.front = self.front.next
			if self.front == None:
				self.rear = None
			return res


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None

	def push(self, item):
		newNode = Node(item)
		if self.head == None:
			self.head = newNode
		else:
			tmp = self.head
			while tmp.next != None:
				tmp = tmp.next
			tmp.next = newNode

	def pop(self):
		if self.head == None:
			return -1
		elif self.head.next == None:
			val = self.head.data
			self.head = None
			return val
		else:
			val = self.head.data
			self.head = self.head.next
			return val


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.last = None

	def push(self, item):
		temp = Node(item)
		if self.head == None:
			self.head = temp
		else:
			x = self.head
			while x.next:
				x = x.next
			x.next = temp

	def pop(self):
		if self.head == None:
			return -1
		x = self.head.data
		self.head = self.head.next
		if self.head:
			self.last = None
		return x


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.front = None
		self.rear = None

	def push(self, item):
		new_node = Node(item)
		if not self.front:
			self.front = new_node
		else:
			self.rear.next = new_node
		self.rear = new_node

	def pop(self):
		if self.front:
			popped_item = self.front
			self.front = self.front.next
			return popped_item.data
		else:
			return -1


class Node:

	def __init__(self, data):
		self.key = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.front = None
		self.rear = None
		self.size = 0

	def push(self, item):
		new_node = Node(item)
		if self.rear == None:
			self.front = new_node
		else:
			self.rear.next = new_node
		self.rear = new_node
		self.size += 1

	def pop(self):
		if self.size == 0:
			return -1
		else:
			res = self.front.key
			self.front = self.front.next
			if self.front == None:
				self.rear = None
			self.size -= 1
			return res


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.sz = 0

	def push(self, item):
		temp = Node(item)
		if self.head == None:
			self.head = temp
			self.sz += 1
			return temp
		curr = self.head
		while curr.next != None:
			curr = curr.next
		curr.next = temp
		self.sz += 1

	def pop(self):
		if self.sz == 0:
			return -1
		res = self.head.data
		self.head = self.head.next
		self.sz -= 1
		return res


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.tail = None

	def push(self, item):
		new_node = Node(item)
		if self.head is None:
			self.head = new_node
			self.tail = new_node
		else:
			self.tail.next = new_node
			self.tail = new_node

	def pop(self):
		if self.head is None:
			return -1
		return_data = self.head.data
		self.head = self.head.next
		return return_data


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.tail = None

	def push(self, item):
		new = Node(item)
		if self.head == None:
			self.head = new
			self.tail = new
		else:
			self.tail.next = new
			self.tail = new

	def pop(self):
		if self.head == None:
			return -1
		x = self.head.data
		self.head = self.head.next
		return x


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class LinkedList:

	def __init__(self):
		self.head = None
		self.tail = None

class MyQueue:

	def __init__(self):
		self.ll = LinkedList()

	def push(self, item):
		Ll = self.ll
		node = Node(item)
		if Ll.head is None:
			Ll.head = node
			Ll.tail = node
		else:
			Ll.tail.next = node
			Ll.tail = node

	def pop(self):
		Ll = self.ll
		if Ll.head is None:
			return -1
		else:
			ans = Ll.head.data
			Ll.head = Ll.head.next
			return ans


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.tail = None

	def push(self, item):
		nn = Node(item)
		if self.tail == None:
			self.head = nn
		else:
			self.tail.next = nn
		self.tail = nn

	def pop(self):
		if self.head == None:
			return -1
		else:
			res = self.head.data
			self.head = self.head.next
			if self.head == None:
				self.tail = None
		return res


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None

	def push(self, item):
		if self.head:
			current = self.head
			while current.next:
				current = current.next
			current.next = Node(item)
		else:
			self.head = Node(item)

	def pop(self):
		if not self.head:
			return -1
		current = self.head.data
		self.head = self.head.next
		return current


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None

	def push(self, item):
		if self.head is None:
			self.head = Node(item)
		else:
			current_node = self.head
			while current_node.next is not None:
				current_node = current_node.next
			current_node.next = Node(item)

	def pop(self):
		if self.head is None:
			return -1
		else:
			a = self.head.data
			self.head = self.head.next
			return a


class MyQueue:

	def __init__(self):
		self.s = []

	def push(self, item):
		self.s.append(item)
		return self.s

	def pop(self):
		if self.s:
			return self.s.pop(0)
		else:
			return -1


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None

	def push(self, item):
		newNode = Node(item)
		if self.head is None:
			self.head = newNode
		else:
			curr = self.head
			while curr.next is not None:
				curr = curr.next
			curr.next = newNode

	def pop(self):
		if self.head is None:
			return -1
		else:
			x = self.head.data
			self.head = self.head.next
			return x


class MyQueue:

	def __init__(self):
		self.q1 = []

	def push(self, item):
		self.q1.append(item)

	def pop(self):
		if len(self.q1) == 0:
			return -1
		x = self.q1.pop(0)
		return x


class MyQueue:

	def __init__(self):
		self.stack = []

	def push(self, item):
		self.stack.append(item)

	def pop(self):
		if len(self.stack) == 0:
			return -1
		else:
			return self.stack.pop(0)


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.front = None
		self.rear = None

	def isEmpty(self):
		return self.front is None

	def push(self, item):
		newNode = Node(item)
		if self.rear is None:
			self.front = newNode
			self.rear = newNode
		else:
			self.rear.next = newNode
			self.rear = newNode

	def pop(self):
		if self.isEmpty():
			return -1
		popped = self.front
		self.front = popped.next
		if self.front is None:
			self.rear = None
		return popped.data


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None

	def push(self, item):
		node = Node(item)
		if self.head is None:
			self.head = node
			return
		ptr = self.head
		while ptr.next is not None:
			ptr = ptr.next
		ptr.next = node
		return

	def pop(self):
		if self.head is None:
			return -1
		if self.head.next is None:
			x = self.head.data
			self.head = None
			return x
		x = self.head.data
		self.head = self.head.next
		return x


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.head = None
		self.tail = None

	def push(self, item):
		newNode = Node(item)
		if self.head == None:
			self.head = newNode
			self.tail = newNode
		else:
			newNode.next = None
			self.tail.next = newNode
			self.tail = newNode

	def pop(self):
		if self.head == None:
			return -1
		elif self.head == self.tail:
			temp = self.head
			self.head = None
			self.tail = None
			return temp.data
		else:
			tempNode = self.head
			self.head = self.head.next
			return tempNode.data


class Node:

	def __init__(self, k):
		self.key = k
		self.next = None

class MyQueue:

	def __init__(self):
		self.front = None
		self.rear = None
		self.sz = 0

	def size(self):
		return self.sz

	def isempty(self):
		return self.sz == 0

	def getfront(self):
		return self.front.key

	def getrear(self):
		return self.rear.key

	def push(self, x):
		temp = Node(x)
		if self.rear == None:
			self.front = temp
		else:
			self.rear.next = temp
		self.rear = temp
		self.sz = self.sz + 1

	def pop(self):
		if self.front == None:
			return -1
		else:
			res = self.front.key
			self.front = self.front.next
			if self.front == None:
				self.rear = None
			self.sz = self.sz - 1
			return res


class Node:

	def __init__(self, value=None):
		self.value = value
		self.next = None

class LinkedList:

	def __init__(self):
		self.head = None
		self.tail = None

	def __iter__(self):
		node = self.head
		while node:
			yield node
			node = node.next

class MyQueue:

	def __init__(self):
		self.list = LinkedList()

	def push(self, item):
		newnode = Node(item)
		if self.list.head is None:
			self.list.head = newnode
			self.list.tail = newnode
		else:
			newnode.next = None
			self.list.tail.next = newnode
			self.list.tail = newnode

	def pop(self):
		ans = self.list.head
		if self.list.head is None:
			return -1
		else:
			self.list.head = self.list.head.next
		return ans.value


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class MyQueue:

	def __init__(self):
		self.front = None
		self.rear = None

	def push(self, item):
		new_node = Node(item)
		if self.rear is None:
			self.front = new_node
			self.rear = new_node
		else:
			self.rear.next = new_node
			self.rear = new_node

	def pop(self):
		if self.front is None:
			return -1
		else:
			popped_node = self.front
			self.front = popped_node.next
			if self.front is None:
				self.rear = None
			return popped_node.data