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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。