剑指offer:用两个栈实现一个队列-创新互联

题目描述
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

目前创新互联已为上1000家的企业提供了网站建设、域名、网站空间、网站托管、服务器租用、企业网站设计、扶余网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。

类似汉诺塔,当我们需要将栈A下面的元素出栈的时候可以先将栈A中的元素全部逆序压入到另一个栈B,这时栈B保存的就是栈A的逆序,也就是满足了FIFO的要求

class Solution:
    """
    用两个栈模拟一个队列,如果两个栈的容量分别为M和N,其中M > N,那么模拟得到的队列的容量是2N+1
    因为假设先把stack2塞满N个,然后此时stack1塞进N+2个,那么此时将元素出队,当stack2的元素全
    部出栈之后,将stack1的后N个元素压入stack2,此时stack1还有2个元素,且这两个元素是即将要出队
    的两个元素,最先要出队的元素在下面,没办法按顺序出队,不满足队列的特性。因此大容量是2N+1
    """
    def __init__(self):
        self.stack1 = []  # stack1用来保存进队的元素
        self.stack2 = []  # stack2用来保存将要出队的元素

    def push(self, node):
        self.stack1.append(node)

    def pop(self):
        if not self.stack1 and not self.stack2:
            return None
        if not self.stack2:  # 当stack2为空的时候将stack1的元素逆序压入
            while self.stack1:
                self.stack2.append(self.stack1.pop(-1))
        return self.stack2.pop(-1)

另外有需要云服务器可以了解下创新互联cdcxhl.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


名称栏目:剑指offer:用两个栈实现一个队列-创新互联
文章路径:http://myzitong.com/article/cscgdo.html