两个栈实现队列和两个队列实现栈-Python实现-复杂度分析

曾经终败给现在 2022-05-31 06:54 195阅读 0赞

\#\#\#两个栈实现一个队列

入队：元素进栈A

出队：先判断栈B是否为空，为空则将栈A中的元素pop出来并push进栈B，再将栈B的第一个元素pop出栈，如不为空则直接从栈B中pop第一个元素出栈

分析：这样做入队的复杂度为O(1)，出队的复杂度则变为O(n)。而直接用python的list实现队列，以list尾为队列首，则入队用insert，复杂度为O(n)，出队用pop，复杂度为O(1)。

class Queue:
        def __init__(self):
            self.stockA=[]
            self.stockB=[]
        def push(self, node):
            self.stockA.append(node)
        def pop(self):
            if self.stockA==[]:
                return None
            if self.stockB==[]:
                for i in range(len(self.stockA)):
                    self.stockB.append(self.stockA.pop())
            return self.stockB.pop()

\#\#\#两个队列实现一个栈

进栈：元素入队A

出栈：判断如果队A只有一个元素，则直接出队。否则，把队A中的元素出队并入队B，直到队A中只有一个元素，再直接出队。

分析：直接用python的list实现栈，以list尾为栈首，则出栈和进栈的复杂度都为O(1)。而用两个队列实现栈，因为进栈要用insert，因此复杂度为O(n)；出栈复杂度为O(n^2)，因为需要连续insert。

class Stock:
        def __init__(self):
            self.queueA=[]
            self.queueB=[]
        def push(self, node):
            self.queueA.insert(0,node)
        def pop(self):
            if self.queueA==[]:
                return None
            while len(self.queueA)!=1:
                self.queueB.insert(0,self.queueA.pop())
            self.queueA,self.queueB=self.queueB,self.queueA
            return self.queueB.pop()

Life is short, You need Python~