算法解剖 - 数据结构篇 - 栈

谁借莪１个温暖的怀抱￠ 2024-04-17 13:53 61阅读 0赞

## 目录 ##

*  1. 栈是一种什么样的数据结构？
 *  2. 栈的实现
 *  3. 栈的应用
    
     *  <1>基于它的LIFO策略，可以逆序排列
     *  <2>模拟计算机实现简单的算术表达式求值

## 1. 栈是一种什么样的数据结构？ ##

栈(下压栈)是一种基于**后进先出**(LIFO:last-in,first-out)策略的集合类型。

现实生活中我们可以把**栈**想象成厨房里摞盘子的架子，后放进去的盘子在最上层，先取用，如下图：

## 2. 栈的实现 ##

使用数组实现栈

JDK中栈的实现类为：java.util.Stack.java，继承了Vector，支持泛型，内部实现是一个对象数组，默认的初始大小为10。

Stack类：
    public class Stack<E> extends Vector<E>
    
    内部实现：
    protected Object[] elementData;
    复制代码

对于Stack类的操作也比较简单，支持如下操作：

## 1.压入操作
    ## 将元素item压入栈顶，返回压入的item元素
    ## 如果现有数组满了，则进行扩容，数组扩大为原来的两倍
    public E push(E item)
    
    ## 2.弹出操作
    ## 将栈顶的元素取出，转成E对象，并返回
    ## 底层Object[]数组原栈顶位置的对象引用置空
    ## 整个操作都是线程安全的，两个线程同时执行的话，其中一个会被阻塞
    public synchronized E pop()
    
    ## 3.查看栈顶的元素（peek翻译过来是‘偷看’的意思）
    ## 只返回栈顶的元素，但栈顶元素不弹出栈
    ## 操作是线程安全的
    public synchronized E peek()
    
    ## 4.判断栈是否为空
    public boolean empty()
    
    ## 5.查询栈中指定的元素
    ## 查询元素o，并返回元素o在栈中的位置（栈顶从1开始向下，到元素o的位置）
    ## 栈中没有元素o时，则返回-1
    ## 操作是线程安全的
    public synchronized int search(Object o)
    复制代码

对于Stack类的search操作，图示举例：

## 3. 栈的应用 ##

栈可以用来做什么用呢？

#### <1> 基于它的LIFO策略，可以逆序排列。 ####

例如：利用栈的结构，可以将给定的字符串逆序输出。

先将字符串每个字符压入栈中，然后再将栈中字符依次弹出，即可得到原字符串的逆序。

代码实现如下：

/**
         * 利用栈结构将给定的字符串逆序输出
         * @param value
         * @return
         */
        public static String reverse(String value) {
            if (value == null || "".equals(value.trim())) {
                return value;
            }
            Stack<Character> stack = new Stack<>();
            for (char c : value.toCharArray()) {
                stack.push(c);
            }
            StringBuilder result = new StringBuilder();
            while (!stack.isEmpty()) {
                result.append(stack.pop());
            }
            return result.toString();
        }
        
        测试：
        System.out.println(StackDemo.reverse("1,2,3,4,5,6"));
        System.out.println(StackDemo.reverse("22 23 24 25 ;"));
        System.out.println(StackDemo.reverse("HH_oo_20190010*/$${}ppXX@##&"));
        输出：
        6,5,4,3,2,1
        ; 52 42 32 22
        &##@XXpp}{$$/*01009102_oo_HH
    复制代码

> ⚠️ 注意：逆序输出不能使用JDK中Stack类的foreach, while + iterator迭代遍历栈中元素，一定要用pop()操作。
> 
> 原因：JDK中Stack类的迭代器，遍历栈中元素，都是从底层对象数组的索引为0处开始，即栈底，而不是栈顶，所以输出的还是原来的顺序。

举例：

Stack<Integer> stack = new Stack<>();
    int[] values = {1,2,3,4,5};
    for (int v : values) {
        stack.push(v);
    }
    
    1.直接输出栈本身：System.out.println(stack);
    结果还是原序：[1, 2, 3, 4, 5]
    
    2.foreach遍历，输出的也是原序：1 2 3 4 5
    for (int s : stack) {
        System.out.println(s);
    }
    
    3.while + iterator遍历，输出的也是原序：1 2 3 4 5
    Iterator iterator = stack.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
    复制代码

#### <2> 模拟计算机实现简单的算术表达式求值 ####

使用两个栈实现，一个保存运算符，一个保存操作数：

处理过程：

*  将操作数压入操作数栈
 *  将运算符压入运算符栈（忽略左括号）
 *  遇到右括号时，弹出一个运算符，弹出所需数量的操作数，进行运算，并将运算的结果压入操作数栈中。

代码实现如下：

/**
     * @author : rangdandanfei
     * @description : 用两个栈(一个保存运算符，一个保存操作数)实现简单的算术表达式求值
     */
    public class CalculateDemo {
        public static void main(String[] args) {
            Stack<String> ops = new Stack<>();
            Stack<Double> vals = new Stack<>();
            Scanner scanner = new Scanner(System.in);
            String s;
            while ((s = scanner.nextLine()) != null && !"".equals(s = s.trim())) {
                if (s.equals("(")) {
                    // 如果字符为"("，则忽略
                } else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("sqrt")) {
                    // 压入运算符
                    ops.push(s);
                } else if (s.equals(")")) {
                    // 如果字符为")"，弹出运算符和所需操作数，进行计算，计算结果压入栈中
                    String op = ops.pop();
                    double v = vals.pop();
                    if (op.equals("+")) {
                        v = vals.pop() + v;
                    } else if (op.equals("-")) {
                        v = vals.pop() - v;
                    } else if (op.equals("*")) {
                        v = vals.pop() * v;
                    } else if (op.equals("/")) {
                        v = vals.pop() / v;
                    } else if (op.equals("sqrt")) {
                        v = Math.sqrt(v);
                    }
                    vals.push(v);
                } else {
                    // 压入操作数
                    vals.push(Double.parseDouble(s));
                }
            }
            System.out.println(vals.pop());
        }
    }
    
    测试输入：(1 + ((2 + 3) * (4 * 5)))
    输出：101.0
    复制代码

转载于:https://juejin.im/post/5d613c9bf265da03c34c06b0