Implement A Queue using Two Stacks Python

问题:

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.

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

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

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

回答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.

回答5:

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)