5.16 Stacks and Queues

Min Stack
思路：
两种解法：
1. 两个栈，一个栈存所有的element, 另一个栈存最小的当前栈中的最小元素，
```java
class MinStack {
Stack stackMin; //store the min element
Stack stack;
//int min; //多余 不需要这个全局最小值， 用stackMin.peek() 来记录全局最小值即可
}

2. 新建一个自定义的数据类型 node 存val, next, min 三个reference

难点在于对stack的 push() 和 pop() 操作的更新。
压入栈的规则：
假设当前数据为newNum, 先将其压入stack, 然后判断stackMin是否为空：
如果stackMin为空，将newNum也压入stackMin
如果不为空，则比较newNum 和stackMin 的栈顶元素中哪一个更小：
如果newNum更小，将newNum也压入stackMin栈中，同时更新min = newNum
如果stackMin的栈顶元素更小，则stackMin不压入元素

弹出栈的元素从上到下依次增大，栈顶元素既为stackMin中的最小值，也同时为全局最小值，
弹出栈的规则：
先弹出stack中的栈顶元素，记作value, 然后比较当前stackMin的栈顶元素和value哪一个最小：
当value == stackMin.peek(), stackMin 弹出栈顶元素
当value > stackMin.peek(), stackMin 不弹出
不会出现value < stackMin.peek() 的情况，因为stackMin.peek() 是两个栈的最小值

CC189 3.3 Stack of Plates
resizing stack??
关键在于对将 stack 扩展之后，两个stack之间如何建立起链接？ 新建一个reference, 指向stack

3.5 Sort Stack
Write a program to sort a stack such that the smallest items are on the top. (use only one tempory stack)
倒水杯
先设定有两个stack, 一个已经sorted 另一个没有sorted，如何将未sorted的stack与已经sorted的stack 合并为一个sorted stack?

Leetcode 20 Valid Parenthesis
左右必定配对，左括号
for (char c : s.toCharArray()) {...}

LeetCode 331. Verify Preorder Serialization of a Binary Tree
必须要做相关处理 剪枝
String[] strs = preorder.split(",");

public class Solution { public boolean isValidSerialization(String preorder) {if (preorder == null) {return false;}String[] strs = preorder.split(','); //must use .split(",") instead of .split(',');Stack<String> stack = new Stack<String>();for (int i = 0; i < strs.length; i++) {String curr = strs[i]; //iterate all the stringwhile (curr.equals("#") && !stack.isEmpty() && stack.peek().equals("#")) {stack.pop();if (stack.isEmpty()) {return false;}stack.pop();}stack.push(curr);}return stack.size() == 1 && stack.peek().equals("#");} }

```

转载于:https://www.cnblogs.com/kong-xy/p/9049695.html

总结

以上是生活随笔为你收集整理的5.16 Stacks and Queues的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。