【算法题】剑指offer之堆和队列--python实现

用两个栈实现队列

题目分析

栈：先进后出
队列：先进先出
完成队列的push和pop操作，即实现头删和尾插。

1. 首先建立两个栈，s1、s2
2. 将队列中的元素“abcd”压入s1中，此时s2为空
3. 将s1中的元素pop进s2中，此时pop一下s2中的元素，就可以达到和队列删除数据一样的顺序了
4. 当s2只pop了一个元素a时（未pop完所有元素），s1中可能还会插入元素e,这时如果将s1中的元素e插入s2中，在a之后出栈的元素就是e了，显然，这样想是不对的，我们必须规定当s2中的元素pop完之后，也就是s2为空时，再插入s1中的元素。

题目分析笔记借鉴于下面的链接：
https://blog.csdn.net/cherrydreamsover/article/details/80466781

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        #append操作为尾插，为了遵循栈的原则，在pop的时候必须是pop()
        self.stack1.append(node)
    def pop(self):
        # return xx
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        #append操作为尾插，为了遵循栈的原则，在pop的时候必须是pop()
        return self.stack2.pop()

滑动窗口的最大值

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        maxli = []
        #有三种情况可以直接返回：
        #num = none
        #size = 0
        #size > len(num)
        if not num or not size or size > len(num):
            return maxli
        for i in range(len(num)-size+1):
            maxli.append(max(num[i:size+i]))
        return maxli