2スタックのPythonでキューを実装し、実行時間を分析してください

Question

私は多くのコーディングのインタビューの質問のいくつかを行ってきました。 私は、Pythonで2つのスタックを使ってキューを実装することについて不思議でした。私は両方のデータ構造を理解するために2つのスタックを持つキューを実装するアルゴリズムの質問に取り組んでいます。 私は以下があります：

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

はこの1つのランタイム分析とは何ですか？

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)