Реализовать очередь с двумя стеками python и проанализировать время работы

Question

Я перебирал некоторые из многих вопросов для интервью по кодированию. Мне было интересно, как реализовать очередь, используя два стека в Python. Я работаю над вопросом алгоритма для реализации очереди с двумя стеками для понимания обеих структур данных. у меня ниже:

class QueueTwoStacks: 

def __init__(self): 
    self.in_stack = [] 
    self.out_stack = [] 

def enqueue(self, item): 
    self.in_stack.append(item) 

def dequeue(self): 
    if len(self.out_stack) == 0: 
     # Move items from in_stack to out_stack, reversing order 
     while len(self.in_stack) > 0: 
      newest_in_stack_item = self.in_stack.pop() 
      self.out_stack.append(newest_in_stack_item) 
     # If out_stack is still empty, raise an error 
     if len(self.out_stack) == 0: 
      raise IndexError("Can't dequeue from empty queue!") 
    return self.out_stack.pop() 

Что является анализ выполнения для этого?

Почему это правда, что мы можем получить O (m) O (m) время выполнения для вызовов функций mm.

Я предполагаю, что имеет реализацию стека и дает O (1) O (1) время толчка и поп?

Я ценю ваше объяснение для этого. Спасибо.

Answer 1

Да. Мы можем оптимизировать временную стоимость m вызовов функций в вашей очереди. Эта оптимизация может быть любым сочетанием вызовов очереди и очереди.

Предположим, что у вас уже есть реализация стека, и она дает O (1) O (1) время push и pop.

#

#

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)