# Queue using LL # Queue using Array

class Node: class Queue:

def __init__(self, data): def __init__(self):
[Link] = data [Link] = []
[Link] = None # [Link] = 0

class Queue: def isEmpty(self):

return [Link] == []
def __init__(self):
[Link] = None def enqueue(self, item):
[Link] = None [Link](0,item)
[Link] = 0 # [Link] += 1

def printme(self): def dequeue(self):

currentPtr = [Link] return [Link]()
q = []
while currentPtr != None: def size(self):
[Link]([Link]) return len([Link])
currentPtr = [Link]
return q # Queue using 2 Stack
class Queue:
def isEmpty(self): def __init__(self):
return [Link] == None self.s1 = []
self.s2 = []
def peek(self):
print( [Link] ) def enQueue(self, x):
# Move all elements from s1 to s2
def EnQueue(self, item): while len(self.s1) != 0:
newData = Node(item) [Link](self.s1[-1])
if [Link] == None: [Link]()
[Link] = [Link] = newData
[Link] += 1 # Push item into self.s1
return [Link](x)

[Link] = newData # Push everything back to s1

[Link] = newData while len(self.s2) != 0:
[Link] += 1 [Link](self.s2[-1])
[Link]()
def DeQueue(self):
if [Link](): def deQueue(self):
print("Queue is Empty") # if first stack is empty
return if len(self.s1) == 0:
currentPtr = [Link] print("Q is Empty")
[Link] = [Link]
[Link] -= 1 # Return top of self.s1
x = self.s1[-1]
if([Link] == None): [Link]()
[Link] = None return x
How to implement a queue using stack? How do you implement stack using
A queue can be implemented using two queues?
stacks. A stack can be implemented using two queues.
We know that stack supports push, pop, and We know that a queue supports enqueue and
peek operations and using these operations, dequeue operations. Using these operations,
we need to emulate the operations of the we need to develop push, pop operations.
queue - enqueue and dequeue. Let stack be ‘s’ and queues used to implement
Let q be the queue and stack1 and stack2 be be ‘q1’ and ‘q2’.
the 2 stacks for implementing q. Then, stack ‘s’ can be implemented in two
ways:
Then queue q can be implemented in two
methods (Both the methods use auxillary
1. By making push operation costly:
space complexity of O(n)):  This method ensures that the newly entered
element is always at the front of ‘q1’ so that
1. By making enqueue operation costly: pop operation just dequeues from ‘q1’.
 Here, the oldest element is always at the top  ‘q2’ is used as auxillary queue to put every
of stack1 which ensures dequeue operation new element in front of ‘q1’ while ensuring
occurs in O(1) time complexity. pop happens in O(1) complexity.
 To place the element at top of stack1, stack2 is
used. Pseudocode:
Pseudocode Push element to stack s: O(n)
Enqueue: Here time complexity will be O(n) push(s, data):
enqueue(q, data): Enqueue data to q2
While stack1 is not empty: Dequeue elements one by one from q1
Push everything from stack1 to stack2 and enqueue to q2.
Push data to stack1 Swap the names of q1 and q2
Push everything back to stack1.
Dequeue: Here time complexity will be O(1) Pop element from stack s: O(1)
deQueue(q): pop(s):
If stack1 is empty then error dequeue from q1 and return it.
else
Pop an item from stack1 and return it
2. By making pop operation costly:
2) By making the dequeue operation costly:  In push operation, the element is enqueued to
 Here, for enqueue operation, the new element q1.
is pushed at the top of stack1. Here, the  In pop operation, all the elements from q1
enqueue operation time complexity is O(1). except the last remaining element, are pushed
 In dequeue, if stack2 is empty, all elements to q2 if it is empty.
from stack1 are moved to stack2 and top  That last element remaining of q1 is dequeued
of stack2 is the result. and returned.
 Basically, reversing the list by pushing to a Pseudocode:
stack and returning the first enqueued element. Push element to stack s: O(1)
This operation of pushing all elements to a push(s,data):
new stack takes O(n) complexity. Enqueue data to q1

Pseudocode: Pop element from stack s: O(n)

Enqueue: Time complexity: O(1) pop(s):
enqueue(q, data):
Push data to stack1 Step1: Dequeue every elements except the
last element from q1 and enqueue to q2.
Dequeue: Time complexity: O(n)
dequeue(q): Step2: Dequeue the last item of q1, the
If both stacks are empty then raise dequeued item is stored in result
error. variable.
If stack2 is empty:
While stack1 is not empty: Step3: Swap the names of q1 and q2 (for
push everything from stack1 to stack2. getting updated data after dequeue)
Pop the element from stack2 and return
it. Step4: Return the result.