用2個堆棧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() 

，這是什麼一個運行時分析？

爲什麼我們可以爲mm函數調用獲得O（m）O（m）運行時。

我假設有一個堆棧實現，它給出O（1）O（1）時間推和流行？

我很感謝您對此的解釋。謝謝。

Answer 1

是的。我們可以優化您的隊列中m個函數調用的時間成本。這種優化可以是入隊和出隊調用的任意組合。

假設你已經有了一個堆棧實現，並且它給出了O（1）O（1）時間的推動和彈出。

＃

＃

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)