5、用两个栈实现队列

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

20、包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

思路：利用一个辅助栈来存放最小值

栈  3，4，2，5，1
辅助栈 3，3，2，2，1

每入栈一次，就与辅助栈顶比较大小，如果小就入栈，如果大就入栈当前的辅助栈顶
当出栈时，辅助栈也要出栈
这种做法可以保证辅助栈顶一定都当前栈的最小值

# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.stack = []self.assist = []def push(self, node)://右边的min()是调用的类内函数用来返回辅助栈的栈顶，就是返回最小值min = self.min()if not min or node < min:self.assist.append(node)else:self.assist.append(min)self.stack.append(node)def pop(self):if self.stack:self.assist.pop()return self.stack.pop()def top(self):# write code hereif self.stack:return self.stack[-1]def min(self):# write code hereif self.assist:return self.assist[-1]

21、栈的压入，弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

直接模拟即可。因为弹出之前的值都会先入栈，所以这里用个栈来辅助。

初始化：用指针i指向pushV的第一个位置， 指针j指向popV的第一个位置
如果pushV[i] != popV[j]， 那么应该将pushV[i]放入栈中， ++i
否则，pushV[i]popV[j], 说明这个元素是放入栈中立马弹出，所以，++i, ++j，然后应该检查popV[j]
与栈顶元素是否相等，如果相等，++j, 并且弹出栈顶元素
4，重复2，3， 如果ipushV.size(), 说明入栈序列访问完，此时检查栈是否为空，如果为空，说明匹配，斗则不匹配。

# -*- coding:utf-8 -*-
class Solution:def IsPopOrder(self, pushV, popV):# write code here# stack中存入pushV中取出的数据stack=[]while popV:# 如果第一个元素相等，直接都弹出，根本不用压入stackif pushV and popV[0]==pushV[0]:popV.pop(0)pushV.pop(0)#如果stack的最后一个元素与popV中第一个元素相等，将两个元素都弹出elif stack and stack[-1] == popV[0]:stack.pop()popV.pop(0)# 如果pushV中有数据，压入stackelif pushV:stack.append(pushV.pop(0))# 上面情况都不满足，直接返回false。else:return Falsereturn True

44、反转单词顺序列

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

思路：以空格为分界符，切分字符串可以得到一个字符串数组，对数字逆序遍历进行拼接。

# -*- coding:utf-8 -*-
class Solution:def ReverseSentence(self, s):# write code herestr_lists = s.split(' ')if len(str_lists) <= 1:return selse:return ' '.join(str_lists[::-1])