[剑指offer] 队列&栈篇

JZ9 用两个栈实现队列

 1 /* 模拟入队 */
 2 public class JZ9_1
 3 {
 4     public static Stack<Integer> stack1 = new Stack<Integer>();
 5     public static Stack<Integer> stack2 = new Stack<Integer>();
 6 
 7     public static void push(int node)
 8     {
 9         if (stack1.isEmpty())
10         {
11             while (!stack2.isEmpty())
12                 stack1.push(stack2.pop());
13             stack2.push(node);
14             while (!stack1.isEmpty())
15                 stack2.push(stack1.pop());
16         }
17     }
18 
19     public static int pop()
20     {
21         return stack2.pop();
22     }
23 }
24 
25 /* ⭐模拟出队⭐ */
26 public class JZ9_2
27 {
28     public static Stack<Integer> stack1 = new Stack<Integer>();
29     public static Stack<Integer> stack2 = new Stack<Integer>();
30 
31     public static void push(int node)
32     {
33         stack1.push(node);
34     }
35 
36     public static int pop()
37     {
38         if (stack2.empty())
39             while (!stack1.empty())
40                 stack2.push(stack1.pop());
41         return stack2.pop();
42     }
43 }

JZ30 包含min函数的栈⭐

 1 /*
 2 * stack: 正常保存每一个入栈的数字
 3 * minStack: 当数字入栈后，保存栈当前状态最小的数
 4 * */
 5 public class JZ30_1
 6 {
 7     public static Stack<Integer> stack = new Stack<>();
 8     public static Stack<Integer> minStack = new Stack<>();
 9 
10     public static void push(int node)
11     {
12         stack.push(node);
13         if (minStack.isEmpty() || node < minStack.peek())
14             minStack.push(node);
15         else
16             minStack.push(minStack.peek());
17     }
18 
19     public static void pop()
20     {
21         stack.pop();
22         minStack.pop();
23     }
24 
25     public static int top()
26     {
27         return stack.peek();
28     }
29 
30     public static int min()
31     {
32         return minStack.peek();
33     }
34 }
35 
36 /*
37  * stack: 正常保存每一个入栈的数字
38  * minStack: 最小元素每一次都进栈，造成重复，所以可以优化成只有当进栈元素≤目前最小元素时，进栈元素才放入最小栈
39  * */
40 public class JZ30_2
41 {
42     public static Stack<Integer> stack = new Stack<>();
43     public static Stack<Integer> minStack = new Stack<>();
44 
45     public static void push(int node)
46     {
47         stack.push(node);
48         if (minStack.isEmpty() || node <= minStack.peek())
49             minStack.push(node);
50     }
51 
52     public static void pop()
53     {
54         if (stack.peek() <= minStack.peek())
55             minStack.pop();
56         stack.pop();
57     }
58 
59     public static int top()
60     {
61         return stack.peek();
62     }
63 
64     public static int min()
65     {
66         return minStack.peek();
67     }
68 }

JZ31 栈的压入、弹出序列

 1 /* 辅助栈 */
 2 public class JZ31_1
 3 {
 4     public static boolean IsPopOrder(int[] pushV, int[] popV)
 5     {
 6         Stack<Integer> sta = new Stack<>();
 7         int idx = 0;
 8         for (int i = 0; i < popV.length; i++)
 9         {
10             while (sta.isEmpty() || sta.peek() != popV[i])
11             {
12                 if (idx == pushV.length) return false;
13                 sta.push(pushV[idx++]);
14             }
15             sta.pop();
16         }
17         return sta.isEmpty();
18     }
19 }
20 
21 /* ⭐原地栈⭐ */
22 public class JZ31_2
23 {
24     public static boolean IsPopOrder(int[] pushV, int[] popV)
25     {
26         int stackTop = -1, idx = 0;
27         for (int i = 0; i < pushV.length; i++)
28         {
29             pushV[++stackTop] = pushV[i];
30             while (stackTop >= 0 && pushV[stackTop] == popV[idx])
31             {
32                 idx++;
33                 stackTop--;
34             }
35         }
36         return idx == popV.length;
37     }
38 }

JZ73 翻转单词序列

 1 /* 字符串翻转 */
 2 public class JZ73_1
 3 {
 4     public static String ReverseSentence(String str)
 5     {
 6         StringBuilder res = new StringBuilder();
 7         String[] s = str.split(" ");
 8         for (int i = s.length - 1; i >= 0; i--)
 9             res.append(s[i] + (i != 0 ? " " : ""));
10         return new String(res);
11     }
12 }
13 
14 /* 滑动窗口 */
15 public class JZ73_2
16 {
17     public static String ReverseSentence(String str)
18     {
19         int left = 0, right = 0;
20         StringBuilder res = new StringBuilder();
21         StringBuilder rev_str = new StringBuilder(str).reverse();
22         while (true)
23         {
24             if (right == rev_str.length() || rev_str.charAt(right) == ' ')
25             {
26                 res.append(new StringBuilder(rev_str.substring(left, right)).reverse());
27                 left = right + 1;
28                 if (right == rev_str.length())
29                     break;
30                 res.append(" ");
31             }
32             right++;
33         }
34         return res.toString();
35     }
36 }
37 
38 /* 栈 */
39 public class JZ73_3
40 {
41     public static String ReverseSentence(String str)
42     {
43         Stack<String> sta = new Stack<String>();
44         StringBuilder res = new StringBuilder();
45         String[] temp = str.split(" ");
46         for (int i = 0; i < temp.length; i++)
47             sta.push(temp[i] + (i == 0 ? "" : " "));
48         while (!sta.isEmpty())
49             res.append(sta.pop());
50         return res.toString();
51     }
52 }

JZ59 滑动窗口的最大值⭐

 1 /* 单调队列 */
 2 public class JZ59_1
 3 {
 4     public static ArrayList<Integer> maxInWindows(int[] num, int size)
 5     {
 6         ArrayList<Integer> res = new ArrayList<>();
 7         Deque<Integer> deque = new LinkedList<>();
 8         if (size == 0) return res;
 9         for (int i = 0; i < num.length; i++)
10         {
11             while (!deque.isEmpty() && num[deque.getLast()] < num[i])
12                 deque.removeLast();
13             deque.addLast(i);
14             if (i - deque.getFirst() >= size) deque.removeFirst();
15             if (i >= size - 1) res.add(num[deque.getFirst()]);
16         }
17         return res;
18     }
19 }