All Courses

# How to Implement a Queue Using Two Stacks in python?

##### By Subham, a year ago

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
##### 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()
```

#### Bootcamp Session : Python for Artificial Intelligence. Oct 2nd (4:00 PM) 173 Registered
More webinars

#### Related Discussions

Running random forest algorithm with one variable

View More