两个栈实现队列和两个队列实现栈-Python实现-复杂度分析-蒲公英云

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

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

入队：元素进栈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()