栈与队列（二）

本小节主要介绍栈与队列的基本应用，将结合实例进行讲解。一、队列的入队与出队操作队列属于一种特殊的线性表，只能在队首或者队尾对其操作。与栈不同的是，它要求先进先出。

例： n个人围成一圈顺序编号，从1号开始按1、2、3......顺序报数，报k者退出圈外，其余的人再从1、2、3开始报数，报k的人再退出圈外，以此类推，其中n、k均为有效值。 请按退出顺序输出每个退出人的原序号。

测试样例：

输入：7 3输出：3 6 2 7 5 1 4

分析：由于是最小的编号开始报数，每次报道k这出队，所以我们可以采用一个队列进行模拟。不过，队尾的后一个人是队首，因此这是一个特殊的队列，即循环队列。当然，由于约瑟夫环中每次出队后存在映射关系，因此本体还有一种采用数学公式的高效解法，有兴趣的可以进一步了解。

代码实现：

class Solution(object): def JosephusCircle(self, n, k): """ :type n, k: int :rtype: List """ res=[] circle=collections.deque() for i in range(n): circle.append(i+1) while len(circle): cnt=k-1 while cnt>0: tmp=circle.popleft() circle.append(tmp) cnt-=1 res.append(circle.popleft()) return res

二、栈的入栈与出栈操作与队列一样，栈也是一种特殊的线性表，它只能在栈顶操作，要求先进后出。

例：给一个字符串只包含'(', ')', '{', '}', '[' 和']'，括号的使用必须符合标准，判断该输入字符串是否是有效的。

测试样例：

"()" 和"()[]{}" 有效的，而 "(]" and "([)]" 是无效的。

分析：这个是典型的栈使用问题，读入一个字符如果它是右半括号，则弹出栈顶与之匹配的左括号，如果这样的左括号不存在或者不为右括号，则将其入栈。最后判断栈是否为空，若为空则匹配，返回true；否则返回false。

代码实现：

class Solution: def isValid(self, s): """ :type s: str :rtype: bool """ if len(s)0: return False return True