1.栈

请你实现一个栈。

操作：

push x：将 加x 入栈，保证 x 为 int 型整数。

pop：输出栈顶，并让栈顶出栈

top：输出栈顶，栈顶不出栈

输入描述：

第一行为一个正整数 n ，代表操作次数。(1 ≤ n ≤ 100000)

接下来的 n ，每行为一个字符串，代表一个操作。保证操作是题目描述中三种中的一种。

输出描述：

如果操作为push，则不输出任何东西。

如果为另外两种，若栈为空，则输出 "error“

否则按对应操作输出。

示例

输入：6
push 1
pop
top
push 2
push 3
pop

输出：1

error

3

题解

import java.util.Scanner;

class Stack{
    int [] data; //保存数据
    int size;	//栈中元素个数
    int maxSize;//栈的最大容量
    int top=0;  //栈顶指针
    
    public Stack(int maxSize){
       this.maxSize=maxSize;
        this.data=new int[maxSize];
    }
    
    public void push(int val){
        if(this.size==this.maxSize){
            System.out.println("error");
        }else{
            data[top++]=val;
            this.size++;
        }
    }
    
    public void top(){
        if(this.size==0){
            System.out.print("error");
        }else{
            System.out.println(data[top-1]);
            this.size--;
        }
    }
    
    public void pop(){
        if(this.size==0){
            System.out.println("error");
        }else{
            System.out.println(data[--top]);
            this.size--;
        }
    }
}

public class Main{
      public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=Integer.valueOf(scanner.nextLine());

        Stack stack = new Stack(n);
        while(scanner.hasNextLine()){
            String string = scanner.nextLine();
            String arr[] = string.split(" ");
            if(arr[0].equals("push")){
                stack.push(Integer.valueOf(arr[1]));
            }else if(arr[0].equals("pop")){
                stack.pop();
            }else{
                stack.top();
            }
        }
    }
}
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

2.栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

示例1

输入：

[1,2,3,4,5],[4,5,3,2,1]
1

复制

返回值：

true
1

复制

说明：

可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true      
1
2

示例2

输入：

[1,2,3,4,5],[4,3,5,1,2]
1

返回值：

false
1

说明：

由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false      
1

思路

方式一： 辅助栈
step 1：准备一个辅助栈，两个下标分别访问两个序列。
step 2：辅助栈为空或者栈顶不等于出栈数组当前元素，就持续将入栈数组加入栈中。
step 3：栈顶等于出栈数组当前元素就出栈。
step 4：当入栈数组访问完，出栈数组无法依次弹出，就是不匹配的，否则两个序列都访问完就是匹配的。

方式二：原地栈
step 1：用下标n表示栈空间，用j表示出栈序列的下标。
step 2：遍历每一个待入栈的元素，加入栈顶，即push数组中n的位置，同时增加栈空间的大小，即n的大小。
step 3：当栈不为空即栈顶n大于等于0，且栈顶等于当前出栈序列，就出栈，同时缩小栈的空间，即减小n。
step 4：最后若是栈空间大小n为0，代表全部出栈完成，否则不匹配。
    
1
2
3
4
5
6
7
8
9
10
11
12

图示：

题解

import java.util.Stack;

public class Solution {

    public static void main(String[] args) {
        int [] a=new int[]{1,2,3,4,5};
        int [] b=new int[]{4,5,3,2,1};

        System.out.println(IsPopOrder(a,b));
        System.out.println(IsPopOrderTwo(a,b));
    }

    public static boolean IsPopOrderTwo(int [] pushA,int [] popA) {
        //表示栈空间的大小，入栈为0
        int left=0;
        //出栈
        int right=0;

        for (int num : pushA) {
            //加入栈项
            pushA[left]=num;
            while(left>=0&&pushA[left]==popA[right]){
                right++;
                left--;
            }
            left++;
        }

        return left==0;
    }

    public static boolean IsPopOrder(int [] pushA,int [] popA) {
        //1.创建stack
        Stack<Integer>stack=new Stack<>();

        //2.定义索引
        int index=0;

        //3.遍历出栈的数组
    for (int i = 0; i < pushA.length; i++) {
    while(index<pushA.length &&(stack.isEmpty()||stack.peek()!=popA[i])){
                stack.push(pushA[index]);
                index++;
            }

            System.out.println(stack);
            if(stack.peek()==(popA[i])){
                stack.pop();
            }else{
                return false;
            }
        }

        return true;
    }
}
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

3.有效括号序列

给出一个仅包含字符’(‘,’)‘,’{‘,’}‘,’[‘和’]',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]"不合法。

数据范围：字符串长度 0\le n \le 100000≤n≤10000

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

示例1

输入：“()[]{}”

返回值：true

示例2

输入：“[]”

返回值：true

示例3

输入：“([)]”

返回值：false

思路

1：创建辅助栈，遍历字符串。
2：每次遇到小括号的左括号、中括号的左括号、大括号的左括号，就将其对应的呦括号加入栈中，期待在后续遇到。
3：如果没有遇到左括号但是栈为空，说明直接遇到了右括号，不合法。
4：其他情况下，如果遇到右括号，刚好会与栈顶元素相同，弹出栈顶元素继续遍历。
5：理论上，只要括号是匹配的，栈中元素最后是为空的，因此检查栈是否为空即可最后判断是否合法
1
2
3
4
5

图示：

题解

import java.util.*;
public class Solution {
    public boolean isValid (String s) {
        //1.定义辅助栈
        Stack<Character>stack=new Stack<>();

        for (int i = 0; i < s.length(); i++) {
             if(s.charAt(i)=='('){
                stack.push(')');
            }
            else if(s.charAt(i)=='['){
                stack.push(']');
            }
            else if(s.charAt(i)=='{'){
                stack.push('}');
            }
            else if(stack.isEmpty()||stack.pop()!=s.charAt(i)){
                return false;
            }
        }
        return stack.isEmpty();
    }
}

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

4.逆波兰表达式求值

给定一个逆波兰表达式，求表达式的值。

数据范围：表达式长度满足 1≤n≤104 ，表达式中仅包含数字和 + ，- , * , / ，其中数字的大小满足∣val∣≤200 。

示例1

输入：[“2”,“1”,“+”,“4”,“*”]

返回值：12

示例2

输入：[“2”,“0”,“+”]

返回值：2

题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串一维数组 
     * @return int整型
     */
    public int evalRPN (String[] tokens) {
        Stack<Integer> stack=new Stack<>();

        for (String token : tokens) {
            String s=token;

            if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
                Integer a = stack.pop();
                Integer b=stack.pop();

               int result=cal(b,s,a);

                stack.push(result);
            }else{
                stack.push(Integer.valueOf(s));
            }

        }
        return stack.pop();
    }
    
    private int cal(Integer a, String opt, Integer b) {
        switch(opt){
            case "+":
                return a+b;
            case "-":
                return a-b;
            case "*":
                return a*b;
            case "/":
                return a/b;
        }
        return 0;
    }
}
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

5. 点击消除

牛牛拿到了一个字符串。
他每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串"abbc"点击后可以生成"ac"。
但相同而不相邻、不相同的相邻字母都是不可以被消除的。
牛牛想把字符串变得尽可能短。他想知道，当他点击了足够多次之后，字符串的最终形态是什么？

输入描述：

一个字符串，仅由小写字母组成。（字符串长度不大于300000）

输出描述：

一个字符串，为“点击消除”后的最终形态。若最终的字符串为空串，则输出0。

示例1

输入：abbc

输出：ac

示例2

输入：abba

输出：0

示例3

输入：bbbbb

输出：b

题解

import java.util.Stack; 
import java.util.Scanner;

public class Main {
    
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
       System.out.println(onclickResult(s));
    }
    
    public static  String onclickResult(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            //相同而不相邻、不相同的相邻字母都是不可以被消除的
            if(!stack.isEmpty()&& stack.peek().equals(s.charAt(i))){
                stack.pop();
            }else{
                stack.push(s.charAt(i));
            }
        }

        StringBuffer result=new StringBuffer();
        while(!stack.isEmpty()){
            result.append(stack.pop());
        }
        return result.toString().length()>0?result.reverse().toString():"0";

    }
}

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

6.表达式求值

请写一个整数计算器，支持加减乘三种运算和括号。

数据范围：0\le |s| \le 1000≤∣s∣≤100，保证计算结果始终在整型范围内

要求：空间复杂度： O(n)O(n)，时间复杂度 O(n)O(n)

示例1

输入：“1+2”

返回值：3

示例2

输入：“(2*(3-4))*5”

返回值：-10

示例3

输入：“3+234-1”

返回值：26

思路

step 1：使用栈辅助处理优先级，默认符号为加号。
step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为int型数字。
step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。
step 4：当遇到符号的时候如果是+，得到的数字正常入栈，如果是-，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈。
step 5：最后将栈中剩余的所有元素，进行一次全部相加。
1
2
3
4
5

图示：

题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        List<Integer>list = getOperationResult(s, 0);
        return list.get(0);
    }
    
    public List<Integer> getOperationResult(String s,int index){
        
      Stack<Integer>stack = new Stack<>();
        int num=0;
        char opt='+';
        int i;
        for(i=index;i<s.length();i++){
            //1.判断是否是数字
            if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
                num=num*10+s.charAt(i)-'0';
                if(i!=s.length()-1){
                  continue;
                }
            }

            //2.获取括号里内容
            if(s.charAt(i)=='('){
                //递归
                List<Integer>list = getOperationResult(s, i + 1);
                num = list.get(0);
                i=list.get(1);
                if(i!=s.length()-1){
                    continue;
                }
            }

            //3.计算内容
            switch(opt){
                case'+':
                    stack.push(num);
                    break;
                case'-':
                    stack.push(-num);
                    break;
                case'*':
                    Integer pop = stack.pop();
                    stack.push(num*pop);
                    break;
            }
            num=0;

            if(s.charAt(i)==')'){
                break;
            }else{
                opt=s.charAt(i);
            }
        }
        int sum=0;

        List<Integer>list = new ArrayList<>();
        while(!stack.isEmpty()){
            sum+=stack.pop();
        }
        list.add(sum);
        list.add(i);
        return list;
    }
}
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