• 数据结构与算法（四）：栈与队列

    栈与队列

    我们一般把栈与队列合在一块讨论，因为他们具有相似的性质。

    栈：栈是限定仅在表尾进行插入和删除操作的线性表，所以栈又称为后进先出（LastIn First Out）的线性表，简称LIFO结构。

    队列：只允许在一端进行插入操作、而在另一端进行删除操作的线性表，队列又称为先进先出（First In First Out）的线性表，简称FIFO结构。

    栈

    生活中的栈

    存储货物或供旅客住宿的地方,可引申为仓库、中转站 。例如我们现在生活中的酒店，在古时候叫客栈，是供旅客休息的地方，旅客可以进客栈休息，休息完毕后就离开客栈。

    image-20221225223718866

    计算机中的栈

    我们把生活中的栈的概念引入到计算机中，就是供数据休息的地方，它是一种数据结构，数据既可以进入到栈中，又可以从栈中出去。
    栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
    我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。

    外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

    栈的设计

    类名Stack
    构造方法Stack()：创建Stack对象
    成员方法public boolean isEmpty()：判断栈是否为空，是返回true，否返回false
    public int size()：获取栈中元素的个数
    public T pop()：弹出栈顶元素
    public void push(E e)：向栈中压入元素e
    成员变量private Node head：记录首结点
    private int n：当前栈的元素个数

    我们一般用链表来实现栈。

    栈的代码实现

    public class Stack<E> implements Iterable<E> {

    /**
     * 头结点
     */
    private final Node<E> head;

    /**
     * 元素个数
     */
    private int count;

    public Stack() {
        this.head = new Node<>();
        this.count = 0;
    }

    /**
     * 插入元素e为新的栈顶元素
     */
    public void push(E e) {
        // 把当前的栈顶元素赋值给新结点的直接后继
        var oldNext = head.next;
        head.next = new Node<>(e, oldNext);
        this.count++;
    }

    /**
     * 出栈
     * 
    
     * 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
     */
    public E pop() {
        var oldNext = head.next;
        if (oldNext == null) {
            return null;
        }
        // 删除首个元素
        head.next = head.next.next;
        count--;

        return oldNext.item;
    }

    /**
     * 判断栈是否为空，是返回true，否返回false
     */
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 获取栈中元素的个数
     */
    public int size() {
        return count;
    }

    @Override
    public Iterator<E> iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator<E> {
        private Node<E> n = head;

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public E next() {
            var node = n.next;
            n = n.next;
            return node.item;
        }
    }

    @NoArgsConstructor
    @AllArgsConstructor
    private static class Node<E> {

        /**
         * 存储元素
         */
        private E item;

        /**
         * 指向下一个节点
         */
        private Node<E> next;
    }
}

    • 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
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94

    栈的应用

    括号匹配问题

    给定一个字符串，里边可能包含"()"小括号和其他字符，请编写程序检查该字符串的中的小括号是否成对出现。

    例如：

    • “(上海)(长安)”：正确匹配
    • “上海((长安))”：正确匹配
    • “上海(长安(北京)(深圳)南京)”：正确匹配
    • “上海(长安))”：错误匹配
    • “((上海)长安”：错误匹配
    public class BracketsMatch {
    public static void main(String[] args) {
        String str = "(上海(长安)())";
        boolean match = isMatch(str);
        System.out.println(str + "中的括号是否匹配：" + match);
    }

    /**
     * 判断str中的括号是否匹配
     *
     * @param str 括号组成的字符串
     * @return 如果匹配，返回true，如果不匹配，返回false
     */
    public static boolean isMatch(String str) {
        return false;
    }
}

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

    请完善isMatch方法

    我们用栈来分析解决方案：

    1. 创建一个栈用来存储左括号
    2. 从左往右遍历字符串，拿到每一个字符
    3. 判断该字符是不是左括号，如果是，放入栈中存储
    4. 判断该字符是不是右括号，如果不是，继续下一次循环
    5. 如果该字符是右括号，则从栈中弹出一个元素t；
    6. 判断元素t是否为null，如果不是，则证明有对应的左括号，如果不是，则证明没有对应的左括号
    7. 循环结束后，判断栈中还有没有剩余的左括号，如果有，则不匹配，如果没有，则匹配

    外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

    代码实现

    public class BracketsMatch {
    private static final char LEFT_PARENTHESIS = '(';
    private static final char RIGIT_PARENTHESIS = ')';

    /**
     * 判断str中的括号是否匹配
     *
     * @param str 括号组成的字符串
     * @return 如果匹配，返回true，如果不匹配，返回false
     */
    public static boolean isMatch(String str) {
        var stack = new Stack<Character>();
        for (int i = 0; i < str.length(); i++) {
            var c = str.charAt(i);
            if (LEFT_PARENTHESIS == c) {
                stack.push(c);
            } else if (RIGIT_PARENTHESIS == c) {
                // 弹出一个元素，如果是NULL，那么证明没有对应的左括号
                if (stack.pop() == null) {
                    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
    • 25
    • 26
    • 27

    逆波兰（后缀）表达式求值

    逆波兰表达式求值问题是我们计算机中经常遇到的一类问题，要研究明白这个问题，首先我们得搞清楚什么是逆波兰表达式？要搞清楚逆波兰表达式，我们得从中缀表达式说起。

    中缀表达式

    中缀表达式就是我们平常生活中使用的表达式，例如：1 + 3 * 2，2 - (1 + 3)等等，中缀表达式的特点是：二元运算符总是置于两个操作数中间。

    中缀表达式是人们最喜欢的表达式方式，因为简单，易懂。但是对于计算机来说就不是这样了，因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做大量的优先级相关操作。

    逆波兰（后缀）表达式

    逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法，后缀表达式的特点：运算符总是放在跟它相关的操作数之后。

    中缀表达式逆波兰表达式
    a+bab+
    a+(b-c)abc-+
    a+(b-c)*dabc-d*+
    a*(b-c)+dabc-*d+

    需求

    给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式，求出该逆波兰表达式的结果。

    public class ReversePolishNotation {
    public static void main(String[] args) {
        //中缀表达式3*（17-15）+18/6的逆波兰表达式如下
        String[] notation = {"3", "17", "15", "-", "*", "18", "6", "/", "+"};
        int result = caculate(notation);
        System.out.println("逆波兰表达式的结果为：" + result);
    }

    /**
     * @param notaion 逆波兰表达式的数组表示方式
     * @return 逆波兰表达式的计算结果
     */
    public static int caculate(String[] notaion) {
        return -1;
    }
}

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

    完善caculate方法，计算出逆波兰表达式的结果。

    我们用栈来分析解决方案：

    1. 创建一个栈对象oprands存储操作数
    2. 从左往右遍历逆波兰表达式，得到每一个字符串
    3. 判断该字符串是不是运算符，如果不是，把该该操作数压入oprands栈中
    4. 如果是运算符，则从oprands栈中弹出两个操作数o1,o2
    5. 使用该运算符计算o1和o2，得到结果result
    6. 把该结果压入oprands栈中
    7. 遍历结束后，拿出栈中最终的结果返回

    外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

    代码实现

    public class ReversePolishNotation {

    /**
     * @param notaion 逆波兰表达式的数组表示方式
     * @return 逆波兰表达式的计算结果
     */
    public static int caculate(String[] notaion) {
        var oprands = new Stack<Double>();
        for (var s : notaion) {
            switch (s) {
                case "+": {
                    var o1 = oprands.pop();
                    var o2 = oprands.pop();
                    oprands.push(o2 + o1);
                }
                break;
                case "-": {
                    var o1 = oprands.pop();
                    var o2 = oprands.pop();
                    oprands.push(o2 - o1);
                }
                break;
                case "*": {
                    var o1 = oprands.pop();
                    var o2 = oprands.pop();
                    oprands.push(o2 * o1);
                }
                break;
                case "/": {
                    var o1 = oprands.pop();
                    var o2 = oprands.pop();
                    oprands.push(o2 / o1);
                }
                break;
                default:
                    // 非运算符，那么入栈
                    oprands.push(Double.parseDouble(s));
            }
        }
        return oprands.pop().intValue();
    }
}

    • 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

    队列

    你们在用电脑时有没有经历过，机器有时会处于疑似死机的状态，鼠标点什么似乎都没用，双击任何快捷方式都不动弹。就当你失去耐心，打算reset时。突然它像酒醒了一样，把你刚才点击的所有操作全部都按顺序执行了一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出，而按先后次序排队等待造成的。

    再比如像移动、联通、电信等客服电话，客服人员与客户相比总是少数，在所有的客服人员都占线的情况下，客户会被要求等待，直到有某个客服人员空下来，才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理。操作系统和客服系统中，都是应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。

    队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

    image-20221225233503324

    队列的设计

    类名Queue
    构造方法Queue()：创建Queue对象
    成员方法public boolean isEmpty()：判断队列是否为空，是返回true，否返回false
    public int size()：获取队列中元素的个数
    public E pop()：从队列中拿出一个元素
    public void push(E e)：往队列中插入一个元素
    成员变量private Node head：记录首结点
    private int n：当前栈的元素个数
    private Node last：记录最后一个结点

    队列的实现

    public class Queue<E> {

    /**
     * 队头指针
     */
    private final Node<E> head;

    /**
     * 队尾指针
     */
    private Node<E> last;
    private int n;

    public Queue() {
        this.head = new Node<>();
        this.last = null;
        this.n = 0;
    }

    /**
     * 入队
     */
    public void push(E e) {
        // 新节点
        var newNode = new Node<>(e, null);
        if (last == null) {
            last = newNode;
            head.next = last;
        } else {
            // 当前尾结点不为NULL
            var oldLast = last;
            last = newNode;
            oldLast.next = last;
        }
        last.next = newNode;
        last = newNode;
        this.n++;
    }

    /**
     * 出队
     */
    public E pop() {
        // 无元素
        if (head == last) {
            return null;
        }
        // 头结点不存储元素，所以移出的元素是头结点下一个元素
        var oldFirst = head.next;
        head.next = oldFirst.next;
        this.n--;
        if (isEmpty()) {
            last = null;
        }
        return oldFirst.item;
    }

    public boolean isEmpty() {
        return n == 0;
    }

    public int size() {
        return n;
    }

    @NoArgsConstructor
    @AllArgsConstructor
    private static class Node<E> {

        /**
         * 存储元素
         */
        private E item;

        /**
         * 指向下一个节点
         */
        private Node<E> next;
    }

}

    • 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
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
  • 相关阅读:
    【Python21天学习挑战赛】-列表 & 元组 & range
    小白零基础自学Java，究竟如何才能学的透彻！
    嵌入式单片机中项目在线仿真工具分享
    【JavaScript】JavaScript、Java 计算两个日期时间内的每一周，不足一周的按照一周计算
    实用类以及枚举
    编译deb包之dh_testdir工具集的应用
    Skill Check: Fundamentals of Large Language Models
    SCI一区级 | Matlab实现GJO-CNN-LSTM-Multihead-Attention多变量时间序列预测
    AM@麦克劳林公式逼近以及误差分析
    学习JAVA的第十二天（基础）
  • 原文地址：https://blog.csdn.net/weixin_44610216/article/details/132735031