about summary refs log tree commit diff
path: root/scratch/facebook/queue-two-stacks.py
blob: a71abeb0055282408979fd2b5c76c722605993c7 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from stack import Stack

class Queue(object):
    def __init__(self):
        self.lhs = Stack()
        self.rhs = Stack()

    def enqueue(self, x):
        self.rhs.push(x)

    def dequeue(self, x):
        y = self.rhs.pop()
        while y:
            self.lhs.push(y)
            y = self.rhs.pop()
        result = self.lhs.pop()
        y = self.lhs.pop()
        while y:
            self.rhs.push(y)
        return result