每日精讲：有效的括号、⽤队列实现栈、⽤栈实现队列

Hello大家好！ 很高兴与大家见面！ 给生活添点快乐，开始今天的编程之路。

一 有效的括号

1题目链接：20. 有效的括号 - 力扣（LeetCode）

2题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

3题目示例：

示例 1： 输入：s = "([])" 输出：true

示例 2： 输入：s = "(]" 输出：false

4题目思路：

解决结构选择：如果括号匹配成功例如{ [ ( ) ] }，我们可以观察每种左括号先进的其对应右括号相对于所有的右括号后出，这与栈的特性一样（先进后出），所有我们这里选择栈来解决这一问题。

基本思路：借助数据结构----栈，遍历字符串，左括号入栈，遇到右括号就跟栈顶元素比较，是否匹配，如果匹配则让栈顶元素出栈，不匹配则返回（false)，记得在返回值之前要销毁栈。

完善思路：一定要记住我们想到的思路不一定适合所有示例，我们一定要想到各种特殊示例，与我们的思路比较，完善其不足。1例如上面我们的基本思路当字符串的第一个元素就是右括号（ ] { } )不适用,所以我们遍历字符串，并且遇到右括号时应先判断栈是否为空，如果此时栈为空则说明这个字符串是以右括号开头，在一定不符合所以返回（flase),记住我们在返回真假的前一步一定要销毁栈。2当我们的括号为奇数个时对于如果是右括号为奇数个时，上面的思路时可行的，但是如果时左括号是奇数个时，即使其余所有欧树个的括号都匹配，但是此时我们的栈中还剩元素未以其对应的右括号匹配，所以我们在退出遍历字符串匹配的循环后，还应判断栈是否为空，如果为空则返回（true)否则返回（flase)。

5题目解决代码【这里我把栈相关的方法全部写入，实际可以不用这么多自己可以选择那些要写那些不要】

二 ⽤队列实现栈

1题目链接：225. 用队列实现栈 - 力扣（LeetCode） 2题目描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

3示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

4题目思路：

先从它们的特性分析栈的特性的先进后出，而队列的特性的先进先出所以我们无法通过一个队列来解决这一问题，我们要通过两队列来解决这个问题。入栈：往不为空的队列中插入数据；出栈：把不为空队列中前size-1个数据娜到另一个队列，再将该队列中最后一个元素出队列；取栈顶元素（不出数据）：取不为空队列中的队尾数据，注意这里为什么不出数据（防止对后续操作的影响）。

5题目解决代码【这里我把队列相关的方法全部写入，实际可以不用这么多自己可以选择那些要写那些不要】

三 ⽤栈实现队列

1题目链接：232. 用栈实现队列 - 力扣（LeetCode）

2题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

3示例：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

4题目思路：

先从它们的特性分析栈的特性的先进后出，而队列的特性的先进先出所以我们无法通过一个队列来解决这一问题，我们要通过两栈来解决这个问题。 但是注意的是这里再取栈顶元素的思想不能和【225. 用队列实现栈 - 力扣（LeetCode）】这道题一样导来到去例如我们入栈的顺序是{1，2，3}，我们利用上面的思想将不为空中前size-1个数据导入另一个栈中第一次取到的是1，但是重复第二次取到的则是3，所以这种思想并不适合这里。这里用的解题思路是一个栈规定用于入栈（插入数据），一个栈规定出栈。入队：往pushST【定用于入栈的栈】中插入数据；出队：popST【规定出栈的栈】不为空直接出数据，否则将pushST中的数据导入到popST后再出数据；取队头：思路和出队一样，只是这里不要pop（不要出栈）。

5题目解决代码【这里我把栈相关的方法全部写入，实际可以不用这么多自己可以选择那些要写那些不要】

好了，今天的内容就分享到这，我们下期再见！