Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

思路：

1.

2.

3.

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

思路:

1. 使用一个和字符串等长的数组，初始化为0。

2. 使用堆栈存放左括号，如果为 '(' 则压入 '(' 所在位置index。

3. 如果是 ')' 且堆栈不为空，则在数组中设置栈顶左括号的位置和当前右括号的位置的值为1. 弹出栈顶。
4. 此时数组中只有0和1，合法的括号，一定是连续的1. 此题变为最大子序列和。为1计算，为0清零。

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

思路：

1. 利用堆栈的性质，为空则压入新值，依次检查字符串中字符与堆栈顶端是否匹配。

2. 匹配则弹出堆栈顶部值，同时不压入新值。

3. 对于所有右键的情况，直接压入。