双栈

[haixiaolu]

思路：

• 创建两个stack， 一个是真正意义上的stack， 一个算是暂时的容器， 在push， pop的时候用来暂时的存入数据

代码 / Python

`class MyQueue:

def __init__(self):

    """
    Initialize a stack and a storage

    """
    self.stack = []
    self.container = []

def push(self, x : int):

    """ Push element x to the end of the stack"""
    while self.stack:

        # put the element that popped from stack to storage
        self.container.append(self.stack.pop())
    self.container.append(x)

        # get the element that popped from storage to stack
    while self.container:
        self.stack.append(self.container.pop())

def pop(self):

    """" Removes the element from in front of queue and returns that element """
    return self.stack.pop()

def peek(self):

    """" Get the front element """
    return self.stack[-1]

def empty(self):

    """ check the queue is empty or not """

    return not bool (self.stack)`

时间复杂度

• Time: O(n) n是栈内数据的长度
• Space: O(n) 两个栈所用的空间