数据结构——栈的实现及应用_栈操作实现及应用的实现

目录
  一、概念
     1. 什么是栈
     2.栈顶、栈底、虚拟机栈、栈帧有什么区别呢？
  二、栈的实现
     1.push()
     2.pop()
     3.peek()
     4.size()
  三、应用场景

一、概念

1. 什么是栈

• 栈 是按照后进先出的原则来进行存储数据的，所以又被称为 后进先出 （Last In First Out） 的线性表，简称 LIFO 。
• 栈 仅限在 栈顶 进行元素的 插入 和 删除 。
  

2.栈顶、栈底、虚拟机栈、栈帧有什么区别呢？

• 栈：描述和组织数据的一种数据结构，先压入的元素在栈底，最后的压入的元素在栈顶；
• Java虚拟机栈: Java方法执行的内存模型；
• 栈帧(Stack Frame): 它是用于支持虚拟机进行方法调用和方法执行的数据结构，每个方法执行的同时会在Java虚拟机栈上创建一个栈帧。

二、栈的实现

我们先准备测试数据：

public T[] elem;
    public int usedSize;

    public MyStack() {
        this.elem =(T[]) new Object[5];
    }
1
2
3
4
5
6

1.push()

将某个元素入栈，并返回。

• 先考虑数组是否满了；
• 如果满，则扩容 Arrays.copyOf，否则在 this.usedSize 位置新增元素；
• 不要忘记 this.usedSize 自增一次。

 public void push(T data) {
        if(isFull()) {
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }

    public boolean isFull() {
       /* if(this.elem.length == this.usedSize) {
            return true;
        }
        return false;*/
        return this.elem.length == this.usedSize;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.pop()

将栈顶元素出栈并返回。

• 先考虑数组是否为空；
• 如果为空，抛出异常，否则先记录 usedSize-1 位置的值；
• 最后 this.usedSize 自减一次，并返回ret值。
  

public T pop() {
        if(empty()) {
            throw new RuntimeException("栈为空");
        }
        T ret = this.elem[usedSize-1];
        this.usedSize--;

        return ret;
    }

    public boolean empty() {
        /*if(this.usedSize == 0) {
           return true;
        }
        return false;*/
        return this.usedSize == 0;
    }

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

3.peek()

获取栈顶元素。

• 先判断数组是否为空。
• 如果为空，抛出异常，否则返回最后一个元素即可。

 public T peek() {
        if(empty()) {
            throw new RuntimeException("栈为空");
        }
        return this.elem[usedSize-1];
    }
1
2
3
4
5
6

4.size()

获取栈中有效元素个数，直接返回 this.usedSize 的值。

public int size() {
        return this.usedSize;
}
1
2
3

三、应用场景

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

思考：

• 先把元素入栈；
• 判断栈顶元素是否和弹出系列元素相等；
• 判断 Stack 是否为空，如果为空，表明正好全部弹出。

代码：

public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed.length == 0 || popped.length == 0) {
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        int j = 0;

        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.empty() && j < popped.length && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
    
        return stack.empty();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

链接：https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof

2.根据逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整1数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

思考：

• 先判断是运算符还是数字；
• 遇到运算符，出栈两次，注意运算顺序(第一次出栈的元素在运算符右边计算)；
• 最后栈顶元素即是逆波兰表达式的值。

代码：

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

        for (int i = 0; i < tokens.length; i++) {
            String ret = tokens[i];
            if(!isWord(ret)) {
               //数字
                stack.push(Integer.valueOf(ret));
            }else {
                //符号
                int right = stack.pop();
                int left = stack.pop();
                switch (ret) {
                    case "+":
                        stack.push(left+right);
                        break;
                    case "-":
                        stack.push(left-right);
                        break;
                    case "*":
                        stack.push(left*right);
                        break;
                    case "/":
                        stack.push(left/right);
                        break;
                }
            }
        }
        return stack.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

链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation

3.给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

思考：

• 判断是否是左括号；
• 判断是否左右括号符合条件；
• 判断 Stack 里面是否为空，如果为空，则字符串有效。

代码：

public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char n = s.charAt(i);
            if(n == '(' || n == '{' || n == '[') {
                stack.push(n);
            }else {
                //右括号开头
                if(stack.empty()) {
                    return false;
                }
                char n2 = stack.peek();
                if(n2 == '(' && n == ')' || n2 == '[' && n == ']' || n2 == '{' && n == '}') {
                    stack.pop();
                }else {
                    return false;
                }

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

链接：https://leetcode.cn/problems/valid-parentheses

这周栈的学习就到这里了，希望大家圣诞节快乐！