World's Best AI Learning Platform with profoundly Demanding Certification Programs
Designed by IITians, only for AI Learners.
How to Implement a Queue Using Two Stacks in python?
By Subham, 2 years ago
Bookmark
0
Given the Stack class below, implement a Queue class using two stacks
Note, this is a "classic" interview problem. Use a Python list data structure as your Stack.
# Uses lists instead of your own Stack class. stack1 = [] stack2 = []
Solution
Fill out your solution below:
class Queue2Stacks(object): def __init__(self): # Two Stacks self.in_stack = [] self.out_stack = [] def enqueue(self, element): # FILL OUT CODE HERE self.in_stack.append(element) pass def dequeue(self): # FILL OUT CODE HERE if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop() pass
Queue
Stack
Python
1 Answer
0
Neha
Solution :
The key insight is that a stack reverses order (while a queue doesn't). A sequence of elements pushed on a stack comes back in reversed order when popped. Consequently, two stacks chained together will return elements in the same order, since reversed order reversed again is original order.
We use an in-stack that we fill when an element is enqueued and the dequeue operation takes elements from an out-stack. If the out-stack is empty we pop all elements from the in-stack and push them onto the out-stack.
class Queue2Stacks(object): def __init__(self): # Two Stacks self.instack = [] self.outstack = [] def enqueue(self,element): # Add an enqueue with the "IN" stack self.instack.append(element) def dequeue(self): if not self.outstack: while self.instack: # Add the elements to the outstack to reverse the order when called self.outstack.append(self.instack.pop()) return self.outstack.pop()
Your Answer
Webinars
Live Masterclass on : "How Machine Get Trained in Machine Learning?"
Jun 1st (5:32 PM) 515 Registered