例题集 栈_栈的例题

1. 用数组实现大小固定的栈
2. 实现一个特殊的栈，在实现栈基本功能的基础上，在实现返回栈中最小元素的操作
3. 用栈结构实现队列结构
4. 删除字符串中所有相邻相同字符
5. 删除最外层括号

1.用数组实现大小固定的栈
思想：

1. 用index指向的位置为下一个数所要存放的地方
2. 若要存放数，先判断是否还能放数，再将index++，把数存进去
3. 若要取数,先判断是否还能取数，再将index–（可以不用把数取出，因为下一个要存进的数会覆盖掉）

    public static class ArrayStack{
        private Integer[] arr;
        private Integer size;

        public ArrayStack(int initSize){
            if (initSize < 0){
                throw new IllegalArgumentException("error");
            }
            arr = new Integer[initSize];
            size = 0;
        }

        //只读不取
        public Integer peek(){
            if (size ==0){
                return null;
            }
            return arr[size-1];
        }

        //放
        public void push(int obj){
            if (size == arr.length){
                throw new ArrayIndexOutOfBoundsException("full");
            }
            arr[size++] = obj;
        }
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

2.实现一个特殊的栈，在实现栈基本功能的基础上，在实现返回栈中最小元素的操作

要求：pop、push、getMin时间复杂度为O(1)，设计的栈类型可以使用现成的栈结构

时间复杂度为O(1)，则getMin时不能遍历数组
1

思路：

1. 准备两个栈，Data栈存放正常数据，Min栈存放最小值
2. 往Data栈中存进数时，比较当前数与Min栈栈顶数大小
   若存进数>Min栈栈顶数 ->往Min栈重复压入栈顶数
   若存进数<Min栈栈顶数 ->往Min栈压入存进数
   

public static void main(String[] args) {
        StackOpration stackOpration = new StackOpration();
        stackOpration.stackData.clear();

        stackOpration.push(1);
        stackOpration.push(3);
        stackOpration.push(1);
        stackOpration.push(3);

        Integer min = stackOpration.getMin();
        System.out.println(min);
    }
    
public static class StackOpration{
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public StackOpration(){
            this.stackData = new Stack<>();
            this.stackMin = new Stack<>();
        }

        //存数
        public void push(int num){
            //第一次存
            if (stackData.isEmpty()){
                stackData.add(num);
                stackMin.add(num);
            }else if (!stackData.isEmpty() && num > stackMin.peek()){
                //存进来的数 > Min栈栈顶
                stackData.add(num);
                stackMin.add(stackMin.peek());
            }else{
                //存进来的数 < Min栈栈顶
                stackData.add(num);
                stackMin.add(num);
            }
        }

        //取数
        public void pop(){
            if (!stackData.isEmpty()){
                stackData.pop();
                stackMin.pop();
            }else {
                throw new RuntimeException("empty");
            }
        }

        //取出最小值
        public Integer getMin(){
            if (!stackMin.isEmpty()){
                return stackMin.peek();
            }else{
                throw new RuntimeException("empty");
            }
        }
    }
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
51
52
53
54
55
56
57
58

3.用栈结构实现队列结构

1. 创建两个栈，stackPush只存放数,stackPop只取出数
2. 只往stackPush中存放数
3. 取出数时，先将stackPush所有数倒进stackPop，弹出stackPop栈顶；再将stackPop所有数倒进stackPush

//仅用栈实现队列结构
public class StackToQueue12 {
    public static void main(String[] args) {

        TwoStackToQueue twoStackToQueue = new TwoStackToQueue();

        twoStackToQueue.push(1);
        twoStackToQueue.push(2);
        twoStackToQueue.push(3);
        twoStackToQueue.push(4);
        twoStackToQueue.push(5);

        Integer pop1 = twoStackToQueue.pop();
        System.out.println(pop1);

        Integer pop2 = twoStackToQueue.pop();
        System.out.println(pop2);

        Integer peek3 = twoStackToQueue.peek();
        System.out.println(peek3);

    }

    public static class TwoStackToQueue{
        private Stack<Integer> stackPush;
        private Stack<Integer> stackPop;

        public TwoStackToQueue(){
            this.stackPop = new Stack<>();
            this.stackPush = new Stack<>();
        }

        //存数
        public void push(int num){
            stackPush.push(num);
        }

        //取数
        public Integer pop(){
            //全局变量 记录返回值
            Integer num;

            //判空
            if (stackPush.isEmpty()){
                throw new RuntimeException("empty");
            }

            //将stackPush所有数倒进stackPop
            while (!stackPush.isEmpty()){
                stackPop.push(stackPush.pop());
            }

            num = stackPop.pop();

            //再将stackPop所有数倒进stackPush
            while (!stackPop.isEmpty()){
                stackPush.push(stackPop.pop());
            }

            return num;
        }

        //只读不取
        public Integer peek(){
            //全局变量 记录返回值
            Integer num;

            //判空
            if (stackPush.isEmpty()){
                throw new RuntimeException("empty");
            }

            //将stackPush所有数倒进stackPop
            while (!stackPush.isEmpty()){
                stackPop.push(stackPush.pop());
            }

            num = stackPop.peek();

            //再将stackPop所有数倒进stackPush
            while (!stackPop.isEmpty()){
                stackPush.push(stackPop.pop());
            }

            return num;
        }
    }
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

4.删除字符串中所有相邻相同字符
题目：
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

思路1
stack
1.用一个stack装入字符
如果与栈顶相同	->	直接删除
如果与栈顶不同	->	加入
2.用一个Sting字符串同步
1
2
3
4
5
6

//时间 5.16%
//空间 5.03%
    public static String removeDuplicates(String s) {
        if (s == null){
            return null;
        }

        Stack<Character> stack = new Stack<>();
        String res = "";

        for (int i = 0;i < s.length();i++){
            char c = s.charAt(i);

            if (!stack.isEmpty() && stack.peek() == c){
                stack.pop();
                res = res.substring(0,res.length() - 1);
                continue;
            }else {
                stack.push(c);
                res += c;
            }
        }


        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

思路2
用StringBuffer代替stack
StringBuffer内部实现了类似stack的入栈出栈操作
1
2
3

//时间 81.61%
//空间 69.98%
    public static String removeDuplicates(String s) {
        if (s == null){
            return null;
        }

        StringBuffer buffer = new StringBuffer();
        int top = -1;
        for (int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            if (top >= 0 && buffer.charAt(top) == c){
                buffer.deleteCharAt(top);
                top--;
            }else {
                buffer.append(c);
                top++;
            }
        }

        return buffer.toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5.删除最外层括号
实例1
输入：s = “(()())(())”
输出："()()()"

实例2
输入：s = “(()())(())(()(()))”
输出："()()()()(())"

//时间 100%
//空间 24.54%
    public static String removeOuterParentheses(String s) {
        if(s == null){
            return null;
        }

        int number = 0;
        StringBuffer stack = new StringBuffer();

        for (char c:
             s.toCharArray()) {

            //如果number > 1 说明这个（非栈底
            if (c == '(' && ++number > 1){
                stack.append(c);
            }
            if (c == ')' && --number > 0){
                stack.append(c);
            }
        }

        return stack.toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//时间 100%
//空间 43.74%
    public static String removeOuterParentheses(String s) {

            StringBuilder sb = new StringBuilder();
            int level = 0;
            for (char c : s.toCharArray()) {
                if (c == ')') --level;
                if (level >= 1) sb.append(c);
                if (c == '(') ++level;
            }
            return sb.toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13