1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class TwoStack {
    public int[] twoStack(int[] ope, int n) {
        if(ope == null || n == 0)
            return null;
        Stack<Integer> stackPush = new Stack<Integer>();
        Stack<Integer> stackPoll = new Stack<Integer>();
        int popCount = 0;//出栈次数
        for(int i = 0; i < n; i++){
            if(ope[i] != 0){
                stackPush.push(ope[i]);
            }else{
                popCount++;
            }
        }
        int[] result = new int[popCount];
        //将stackPush栈中的所有数据导入到stackPoll栈中
        while(!stackPush.empty()){
            stackPoll.push(stackPush.pop());
        }
        for(int i = 0; i < popCount; i++){
            result[i] = stackPoll.pop();
        }
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class StackReverse {
    //反转栈
    public static int[] reverseStack(int[] A, int n) {
        if(A == null || n == 0)
            return null;
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0; i < n; i++){
            stack.push(A[i]);
        }
        reverse(stack);//开始反转操作
        for(int i = n-1; i >= 0; i--){
            A[i] = stack.pop();
        }
        return A;
    }

    /**
     * 反转栈中的元素
     * @param stack
     */
    public static void reverse(Stack<Integer> stack){
        if(stack.isEmpty()){
            return ;
        }
        //下面就是先递归拿到栈底元素，然后再把栈底元素入栈，此时栈中元素顺序反转
        int bottom = popBottom(stack);
        reverse(stack);
        stack.push(bottom);
    }

    /**
     * 移除栈底元素，并返回
     * @return
     */
    public static int popBottom(Stack<Integer> stack){
        int result = stack.pop();
        if(stack.isEmpty()){//弹出一个栈顶元素后，栈为空了，表示该元素就是栈底元素
            return result;
        }else{
            int last = popBottom(stack);
            stack.push(result);//注意！！！这里是把前面拿到的元素压入，这样栈底元素才不会再次压入到栈中
            return last;
        }
    }
   
    public static void main(String[] args) {
        int[] a = {9,8,7,6,5,4,3,2,1};
        reverseStack(a,a.length);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static ArrayList<Integer> twoStacksSort(int[] numbers) {
        if(numbers == null)
            return null;
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = numbers.length - 1; i >= 0; i--){
            stack.push(numbers[i]);
        }
        Stack<Integer> help = new Stack<Integer>();
        int pop,temp;
        while(!stack.isEmpty()){
            pop = stack.pop();
            if(help.isEmpty()){
                help.push(pop);
            }else{
                if(pop <= help.peek()){
                    help.push(pop);
                }else{
                    while(!help.isEmpty() && pop > help.peek()){//将help中元素放入到stack中
                        temp = help.pop();
                        stack.push(temp);
                    }
                    //help栈为空了或者找到了pop<=help栈顶的元素
                    help.push(pop);
                }
            }
        }
        while(!help.isEmpty()){
            stack.push(help.pop());
        }
        ArrayList<Integer> res = new ArrayList<Integer>();
        while(!stack.isEmpty()){
            res.add(stack.pop());
        }
        return res;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
     * 数组作为栈，0的位置为栈顶
     * @param numbers
     * @return
     */
    public static ArrayList<Integer> twoStacksSort2(int[] numbers) {
        if(numbers == null)
            return null;
        int[] help = new int[numbers.length];
        int i = 0;//指向numbers栈顶元素
        int j = -1;//指向help栈顶元素
        int pop;
        while(i >= 0 && i != numbers.length){
            pop = numbers[i];
            if(j < 0){
                help[++j] = pop;
            }else{
                if(pop <= help[j]){
                    help[++j] = pop;
                }else{
                    while(j >= 0 && pop > help[j]){
                        numbers[i--] = help[j--];
                    }
                    help[++j] = pop;
                }
            }
            i++;
        }
        ArrayList<Integer> res = new ArrayList<Integer>();
        for (int k = 0; k < help.length; k++) {
            res.add(help[k]);
            System.out.println(help[k]);
        }
        return res;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static int[] slide(int[] arr, int n, int w) {
        if(arr == null || w < 1 || n < w){
            return null;
        }
        int[] res = new int[n - w + 1];
        //一个维护w个窗口的双端队列，保持下标为对头元素的值最大
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int index = 0;
        for(int i = 0; i < n; i++){
            //执行队尾进入规则
            while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){
                qmax.pollLast();
            }
            qmax.addLast(i);//将下标加入到队尾
            //执行对头弹出规则
            if(qmax.peekFirst() == i - w){
                qmax.pollFirst();
            }
            if(i >= w - 1){//如果双端队列里面至少维持了w个数据，则每次可以从对头中拿到最大值
                res[index++] = arr[qmax.peekFirst()];
            }
        }

        return res;
    }