I've been going over some of the many coding interview questions. I was wondering how you would go about implementing a queue using two stacks in Python? Python is not my strongest language so I need all the help I can get.
Like the enqueue, dequeue, and front functions.
class Queue(object):
def __init__(self):
self.instack=[]
self.outstack=[]
def enqueue(self,element):
self.instack.append(element)
def dequeue(self):
if not self.outstack:
while self.instack:
self.outstack.append(self.instack.pop())
return self.outstack.pop()
q=Queue()
for i in range(10):
q.enqueue(i)
for i in xrange(10):
print q.dequeue(),
class MyQueue(object):
def __init__(self):
self.first = []
self.second = []
def peek(self):
if not self.second:
while self.first:
self.second.append(self.first.pop());
return self.second[len(self.second)-1];
def pop(self):
if not self.second:
while self.first:
self.second.append(self.first.pop());
return self.second.pop();
def put(self, value):
self.first.append(value);
queue = MyQueue()
t = int(raw_input())
for line in xrange(t):
values = map(int, raw_input().split())
if values[0] == 1:
queue.put(values[1])
elif values[0] == 2:
queue.pop()
else:
print queue.peek()
class Stack:
def __init__(self):
self.elements = []
def push(self, item):
self.elements.append(item)
def pop(self):
return self.elements.pop()
def size(self):
return len(self.elements)
def is_empty(self):
return self.size() == 0
class CreatingQueueWithTwoStacks:
def __init__(self):
self.stack_1 = Stack()
self.stack_2 = Stack()
def enqueue(self, item):
self.stack_1.push(item)
def dequeue(self):
if not self.stack_1.is_empty():
while self.stack_1.size() > 0:
self.stack_2.push(self.stack_1.pop())
res = self.stack_2.pop()
while self.stack_2.size() > 0:
self.stack_1.push(self.stack_2.pop())
return res
if __name__ == '__main__':
q = CreatingQueueWithTwoStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
a = q.dequeue()
print(a)
b = q.dequeue()
print(b)
c = q.dequeue()
print(c)
d = q.dequeue()
print(d)
q.enqueue(5)
q.enqueue(6)
print(q.dequeue())
First, create a stack object. Then create a queue out of 2 stacks. Since a Stack = FIFO (first in first out), and Queue = LIFO (last in first out), add all the items to the "in stack" and then pop them into the output.
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
class Queue2Stacks(object):
def __init__(self):
# Two Stacks
self.in_stack = Stack()
self.out_stack = Stack()
def enqueue(self, item):
self.in_stack.push(item)
def dequeue(self):
if self.out_stack.is_empty:
while self.in_stack.size()>0:
self.out_stack.push(self.in_stack.pop())
return self.out_stack.items.pop()
#driver code
q = Queue2Stacks()
for i in range(5):
q.enqueue(i)
for i in range(5):
print(q.dequeue(i))
Gives you 0,1,2,3,4
Stack1, Stack2.
Enqueue:
Push el into stack1.
Dequeue:
While (!empty(Stack1))
el = Pop from stack1
Push el into stack2
returnEl = Pop from Stack2
While (!empty(Stack2))
el = Pop from stack2
Push el into stack1
return returnEl
That is a way of implementing the algorithm in pseudocode, it shouldn`t be difficult to implement it in python knowing the basic syntax.
I found this solution that works for implementing a queue using two stacks. I use set instead of queue. We can use the following implementation. for the time cost of m function calls on your queue. This optimization can be any mix of enqueue and dequeue calls.
#
#
class Stack():
def __init__(self):
self.stk = []
def pop(self):
"""raises IndexError if you pop when it's empty"""
return self.stk.pop()
def push(self, elt):
self.stk.append(elt)
def is_empty(self):
return len(self.stk) == 0
def peek(self):
if not self.stk.is_empty():
return self.stk[-1]
class Queue():
def __init__(self):
self.q = Stack() # the primary queue
self.b = Stack() # the reverse, opposite q (a joke: q vs b)
self.front = None
def is_empty(self):
return self.q.is_empty()
def peek(self):
if self.q.is_empty():
return None
else:
return self.front
def enqueue(self, elt):
self.front = elt
self.q.push(elt)
def dequeue(self):
"""raises IndexError if you dequeue from an empty queue"""
while not self.q.is_empty() > 0:
elt = self.q.pop()
self.b.push(elt)
val = self.b.pop()
elt = None
while not self.b.is_empty() > 0:
elt = self.b.pop()
self.q.push(elt)
self.front = elt
return val
# Now let's test
class TestQueueTwoStacks(unittest.TestCase):
def setUp(self):
self.q = Queue()
def test_queuedequue(self):
"""queue up 5 integers, check they are in there, dequeue them, check for emptiness, perform other blackbox and whitebox tests"""
self.assertTrue(self.q.is_empty())
self.assertTrue(self.q.q.is_empty())
self.assertTrue(self.q.b.is_empty())
l = range(5)
for i in l:
self.q.enqueue(i)
self.assertEqual(4, self.q.peek())
self.assertEqual(l, self.q.q.stk)
s = []
l.reverse()
for i in l:
elt = self.q.dequeue()
s.append(elt)
self.assertTrue(self.q.is_empty())
self.assertTrue(self.q.q.is_empty())
self.assertTrue(self.q.b.is_empty())
l.reverse()
self.assertEqual(s, l)
self.assertEqual([], self.q.b.stk)
self.assertEqual([], self.q.q.stk)
if __name__ == "__main__":
# unittest.main()
suite = unittest.TestLoader().loadTestsFromTestCase(TestQueueTwoStacks)
unittest.TextTestRunner(verbosity=2).run(suite)
