栈模拟

# 逆序栈

使用递归将栈中元素逆序放置；

public void reverseStack(Stack<Integer> stack){
    if(stack.isEmpty()){
        return ;
    }
    int bottom = f(stack);
    reverseStack(stack);
    stack.push(bottom);
}
//移除栈底元素并返回
int f(Stack<Integer> stack){
    int ele = stack.pop();
    if(stack.isEmpty()){
        return ele;
    }else{
        int bottom = f(stack);
        stack.push(ele);
        return bottom;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 394. 字符串解码 (opens new window)

方法一：辅助队列

方法二：递归

class Solution {
    public String decodeString(String s) {
        return dfs(s,0)[0];
    }
    String[] dfs(String s,int i){
        StringBuilder sb = new StringBuilder();
        int mul = 0;
        while(i<s.length()){
            if(s.charAt(i)>='0' && s.charAt(i)<='9'){
                mul = mul*10 + Integer.parseInt(String.valueOf(s.charAt(i)));
            }else if(s.charAt(i)=='['){
                String[] tmp = dfs(s,i+1);
                i = Integer.parseInt(tmp[0]);
                while(mul>0){
                    sb.append(tmp[1]);
                    mul--;
                }
            }else if(s.charAt(i)==']'){
                // ']'的索引i位置，括号内的sb
                return new String[]{String.valueOf(i),sb.toString()};
            }else{
                sb.append(String.valueOf(s.charAt(i)));
            }
            i++;
        }
        return new String[]{sb.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
25
26
27
28

# 20. 有效的括号 (opens new window)

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c=='(')
                stack.push(')');
            else if(c=='[')
                stack.push(']');
            else if(c=='{')
                stack.push('}');
            else if(stack.isEmpty() || c!=stack.peek())
                return false;
            else 
                stack.pop();
        }
        return stack.isEmpty();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 32. 最长有效括号 (opens new window)

class Solution {
    public int longestValidParentheses(String s) {
        int ret = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else{
                    ret = Math.max(ret,i-stack.peek());
                }
            }
        }
        return ret;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 71. 简化路径 (opens new window)

class Solution {
    public String simplifyPath(String path) {
        String[] ss = path.split("/");
        Stack<String> stack = new Stack<>();
        for(String s:ss){
            if(s.equals(".")||s.length()==0){
                continue ;
            }else if(s.equals("..")){
                if(!stack.isEmpty()){
                    stack.pop();
                }
                continue ;
            }else{
                stack.push(s);
            }
        }
        String ret = "";
        while(!stack.isEmpty()){
            ret = "/"+stack.pop()+ret;
        }
        return ret.isEmpty()?"/":ret;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 155. 最小栈 (opens new window)

方法一：辅助栈

class MinStack {

    Stack<Integer> smaller = new Stack<>();
    Stack<Integer> stack = new Stack<>();

    public MinStack() {

    }
    
    public void push(int val) {
        stack.push(val);
        if(smaller.isEmpty() || val<=smaller.peek()){
            smaller.push(val);
        }
    }
    
    public void pop() {
        if(stack.peek().equals(smaller.peek())){
            smaller.pop();
        }
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return smaller.peek();
    }
}

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

方法二：一个栈

class MinStack {

    // 当前值，之前最小值
    Stack<int[]> stack = new Stack<>();

    public MinStack() {

    }
    
    public void push(int val) {
        if(stack.isEmpty()){
            stack.push(new int[]{val,val});
        }else{
            stack.push(new int[]{val,Math.min(val,stack.peek()[1])});
        }
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek()[0];
    }
    
    public int getMin() {
        return stack.peek()[1];
    }
}

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

← 单调队列优先级队列→