Implement A Queue using Two Stacks Python

Question

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.

Solution 1

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(),

Solution 2

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

Solution 3

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

Solution 4

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

View more solutions