[数据结构][Python]用两个栈实现队列与用两个队列实现栈

àì夳堔傛蜴生んèń 2022-10-02 15:55 227阅读 0赞

# 题目 #

用栈模拟一个队列，实现入队、出队

# 解决方案 #

让元素1入队

让元素2入队

让元素3入队

这个时候，希望最先入队的1出队。让栈A中的所有元素按顺序出栈，再按照出栈顺序压入栈B

让1出队

…

class QueueWithTwoStacks(object):
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
    
        def appendTail(self,x):
            self.stack1.append(x)
    
        def deleteHead(self):
             if self.stack2:
                 return self.stack2.pop()
             else:
                 if self.stack1:
                    while self.stack1:
                        self.stack2.append(self.stack1.pop())
                    return self.stack2.pop()
                 else:
                     return None

# 扩展 #

用两个队列实现栈：

class StackWithTwoQueues(object):
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
    
        def push(self,x):
            if len(self.stack1) == 0:
                self.stack1.append(x)
            elif len(self.stack2) == 0:
                self.stack2.append(x)
            if len(self.stack2) == 1 and len(self.stack1) >= 1:
                while self.stack1:
                    self.stack2.append(self.stack1.pop(0))
            elif len(self.stack1) == 1 and len(self.stack2) > 1:
                while self.stack2:
                    self.stack1.append(self.stack2.pop(0))
    
        def pop(self):
            if self.stack1:
                return self.stack1.pop(0)
            elif self.stack2:
                return self.stack2.pop(0)
            else:
                return None