数据结构与算法_03_栈

数据结构与算法
发布日期:   2021-10-16
更新日期:   2021-10-26
文章字数:   2.5k
阅读时长:   10 分
阅读次数:  

本文介绍一个和队列很相似的数据结构——栈。

1. 栈理论基础

1.1 栈

上文中提到，队列是在数组的基础上加了限制。此时对数组需要另一种限制，只能在一端进行存取，其他位置是不可访问的，这种新形成的数据结构就是栈。

简单地说，栈就是“后进先出”，即最后进入栈的数据，最先出去。向栈中插入元素，只能在栈顶插入（入栈）；访问栈中的元素或者删除栈中的元素，只能在栈顶中一个个访问并删除（出栈）。

DSAA_010.png (463×119) (gitee.io)

栈这种数据结构也比较简单，提供的方法主要有入栈、出栈、访问元素（不出栈）、获取当前栈长（元素个数）等等。

1.2 栈的Java实现

既然栈也是在数组的基础上加了限制，那么可以先用数组实现一下栈；另外队列也是可以实现栈的；同时Java中也提供了栈这种数据结构。

1.2.1 数组实现栈

实现代码如下，为了存储多种数据类型，这里采用了Object父类，即多态：

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
class Stack{
    private Object[] stack;
    private int index;

    public Stack(){}

    public Stack(int num){
        this.stack = new Object[num];
        this.index = 0;
    }

    public void push(Object obj){

        if(this.index >= this.stack.length){
            System.out.println("压栈失败，栈已满！");
        }else{
            stack[this.index] = obj;
            this.index++;
        }
    }

    public Object pop(){
        if(this.index <= 0){
            System.out.println("弹栈失败，栈已空");
            return null;
        }else{
            Object obj = stack[this.index - 1];
            this.index--;
            return obj;
        }
    }

    public int size(){
        return this.index;
    }
}

1.2.2 队列实现栈

一个简单的思路是，入栈的时候用队列保存数据，弹栈的时候将队列出队然后再入队，只对最后一个元素出队。实现代码如下（其中Queue是上一篇文章中实现的Queue）：

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
class Stacks{
    
    private Queue queue;

    public Stacks(){}

    public Stacks(int length){
        this.queue = new Queue(length);
    }

    public void push(Object obj){
        this.queue.push(obj);
    }

    public Object pop(){
        int length = this.getCurrentLength();
        for (int i = 0; i < length - 1; i++) {
            this.queue.push(this.queue.pop());
        }

        return this.queue.pop();
    }

    public int getCurrentLength(){
        return this.queue.getCurrentLength();
    }

    public Object get(){

        if(this.queue.getCurrentLength() != 0){
            Object obj = this.pop();
            this.push(obj);

            return obj;
        }
        return null;
    }
}

1.2.3 Java提供的栈

Java中提供了栈类java.util.Stack。

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
import java.util.Stack;

public class StackTest02 {

    public static void main(String[] args) {

        Stack<String> stack = new Stack<String>();

        stack.push("hello");
        stack.push("world");

        System.out.println(stack.isEmpty());
        System.out.println(stack.size());

        System.out.println("===========");

        System.out.println(stack.pop());
        System.out.println(stack.size());

        System.out.println("===========");

        System.out.println(stack.pop());
//        System.out.println(stack.pop());
        System.out.println(stack.size());
    }
}

2. 栈经典题目

2.1 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 注意空字符串可被认为是有效字符串。

示例 1:

  • 输入: “()”
  • 输出: true

示例 2:

  • 输入: “()[]{}”
  • 输出: true

示例 3:

  • 输入: “(]”
  • 输出: false

示例 4:

  • 输入: “([)]”
  • 输出: false

示例 5:

  • 输入: “{[]}”
  • 输出: true

这道题括号不匹配主要有三种情况，左侧括号多，右侧括号多，括号不匹配。

可以用栈来解决，判断当前字符是否是左侧括号，如果是，则直接入栈，如果不是则将当前字符与栈顶字符比较是否匹配，如果匹配则继续，如果不匹配则说明字符串不满足要求，返回false；或者当前字符是右侧括号，而栈空，则说明右侧括号多。如果匹配结束之后，栈中还有数据则说明左侧括号多。

左侧括号入栈方法如下：

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
public static boolean solution_1(String argss){
        String left = "({[";
        String right = ")}]";

        boolean result = true;

        Stack<Character> stack = new Stack<Character>();

        for (int i = 0; i < argss.length(); i++) {

            if(left.indexOf(argss.charAt(i)) != -1){
                // 当前括号是左侧，直接入栈
                stack.push(argss.charAt(i));
            }
            else{
                // 当前括号是右侧，判断是否匹配栈顶元素，不匹配则直接退出。匹配则弹栈。
                if(stack.isEmpty() || right.indexOf(argss.charAt(i)) != left.indexOf(stack.peek())){
                    result = false;
                    break;
                }
                stack.pop();
            }
        }
        // 如果循环结束之后，栈中还有元素，说明没有匹配完，字符串不满足要求
        if(!stack.isEmpty()){
            result = false;
        }

        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
public static boolean solution_2(String argss){

        String left = "({[";
        String right = ")}]";

        int leftIndex;
        boolean result = true;

        Stack<Character> stack = new Stack<Character>();

        for (int i = 0; i < argss.length(); i++) {

            leftIndex = left.indexOf(argss.charAt(i));

            // 当前是左括号，并把对应的有括号压栈
            if(leftIndex != -1){
                stack.push(right.charAt(leftIndex));
            }
            else{
                // 当前是有括号，弹栈匹配
                if(stack.isEmpty() || argss.charAt(i) != stack.pop()){
                    result = false;
                    break;
                }
            }
        }

        if(!stack.isEmpty()){
            result =false;
        }

        return result;
    }

2.2 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

  • 输入：”abbaca”
  • 输出：”ca”
  • 解释：例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

提示：

  • 1 <= S.length <= 20000
  • S 仅由小写英文字母组成。

这道题仍然可以用栈来做，遍历字符串，每遍历一次就查看是否匹配栈顶元素，如果匹配，则将栈顶元素删除，并继续遍历；如果不匹配则将入栈。遍历结束后，返回栈中的元素（注意字符的顺序）。实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static String solution_1(String args){
        Stack<Character> stack = new Stack<Character>();

        StringBuilder strs = new StringBuilder();

        for (int i = 0; i < args.length(); i++) {

            if(stack.isEmpty() || stack.peek() != args.charAt(i)){
                // 栈空 则 入栈
                stack.push(args.charAt(i));
            }
            else{
                // 否则 判断是否匹配
                stack.pop();
            }
        }

        while(!stack.isEmpty()){
            strs.insert(0, stack.pop());
        }

        return strs.toString();
    }

另外，也可以直接用字符串来做，遍历字符串，每次遍历都比较新字符串末尾元素，如果相同，则删除新字符串中该元素，如果不相同则直接追加即可。采用字符串直接省略了后续栈转换为字符串的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static String solution_2(String args){
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < args.length(); i++) {

            if(result.length() == 0 || result.charAt(result.length() - 1) != args.charAt(i)){
                result.append(args.charAt(i));
            }else{
                result.deleteCharAt(result.length() - 1);
            }
        }

        return result.toString();
    }

还有一种方法是采用双指针来做，即保留两个索引，一个用于遍历，一个用于存储新的字符串（在旧字符串的基础上）。注意，一定要用慢指针来判断是否重复，如果用快指针的话，重复一次之后无法判断以前的是否重复（如assa类型，快指针判断ss之后，无法判断a和a重复，因为快指针是原始字符串），代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static String solution_3(String args){

        int fast = 0, slow = 0;
        char[] newCh = args.toCharArray();

        while(fast < newCh.length){

            newCh[slow] = newCh[fast];

            if(slow > 0 && newCh[slow] == newCh[slow - 1]) {
                slow--;
            }else{
                slow++;
            }
            fast++;
        }

        return new String(newCh, 0, slow);
    }

2.3 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

  • 输入: [“2”, “1”, “+”, “3”, “ * “]
  • 输出: 9
  • 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

  • 输入: [“4”, “13”, “5”, “/“, “+”]
  • 输出: 6
  • 解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

  • 输入: [“10”, “6”, “9”, “3”, “+”, “-11”, “ * “, “/“, “ * “, “17”, “+”, “5”, “+”]

  • 输出: 22

  • 解释:该算式转化为常见的中缀算术表达式为：

    1
    2
    3
    4
    5
    6
    7
    ((10 * (6 / ((9 + 3) * -11))) + 17) + 5       
    = ((10 * (6 / (12 * -11))) + 17) + 5       
    = ((10 * (6 / -132)) + 17) + 5     
    = ((10 * 0) + 17) + 5     
    = (0 + 17) + 5    
    = 17 + 5    
    = 22

逆波兰表达式：是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

  • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

该题和删除重复项类似，而且这些运算符都是二元，所以只需要在判断完运算符之后，弹栈两次计算结果并将结果入栈，注意除法运算的因子顺序。代码如下所示：

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
public static int solution_1(String[] args){

        Stack<Integer> strs = new Stack<Integer>();

        int firstFactor, secondFactor;

        for (int i = 0; i < args.length; i++) {
            if(args[i].equals("+")){

                strs.push(strs.pop() + strs.pop());

            }else if(args[i].equals("-")){

                strs.push(strs.pop() - strs.pop());

            }else if(args[i].equals("*")){

                strs.push(strs.pop() * strs.pop());

            }else if(args[i].equals("/")){
                secondFactor = strs.pop();
                firstFactor = strs.pop();
                strs.push(firstFactor / secondFactor);

            }else{
                strs.push(Integer.parseInt(args[i]));
            }
        }

        return strs.pop();
    }

3. 备注

部分参考代码随想录 (programmercarl.com)。

文章作者: 浮云
文章链接: https://ihianian.github.io/2021/10/16/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-03-%E6%A0%88/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
数据结构与算法
赏
  目录