（JAVA）浅尝关于 “栈” 数据结构

1. 栈的概述：

1.1 生活中的栈

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

1.2计算机中的栈

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

在这里插入图片描述

2. 栈的实现

2.1 栈API设计

类名	Stack
构造方法	Stack()：创建Stack对象
成员方法	1. public boolean isEmpty()：判断栈是否为空，是返回true，否返回false 2. public int size()：获取栈中元素的个数 3. public T pop()：弹出栈元素 4. public void push(T t)：向栈中压入元素t
成员变量	1. private Node head：记录首节点 2. private int N：当前栈的元素个数
成员内部类	private class Node：节点类

2.2 代码实现

package com.renexdemo.linear;

import java.util.Iterator;

public class Stack<T> implements Iterable<T> {
    private Node head;
    private int N;

    // 节点类
    private static class Node<T>{
        public T item;// 存储元素
        public Node next;// 指向下一个节点

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    // 初始化栈
    public Stack() {
        this.head = new Node(null,null);
        this.N = 0;
    }

    // 判断栈是否为空
    public boolean isEmpty(){
        return N == 0;
    }
    // 获得栈中的数量
    public int size(){
        return N;
    }
    // 压栈
    public void push(T t){
        // 找到首节点指向的第一个节点
        Node oldNode = head.next;
        // 创建新节点
        Node<T> newNode = new Node<>(t, null);
        // 让首节点指向新节点
        head.next = newNode;
        // 让新节点指向原来的第一个节点
        newNode.next = oldNode;
        // 元素个数+1
        N++;
    }
    // 弹栈
    public T pop(){
        // 找到首节点指向的第一个节点
        Node oldFirst = head.next;

        if (oldFirst == null){
            return null;
        }
        // 让首节点指向原来第一个节点的下一个节点
        head.next=oldFirst.next;

        // 元素个数-1
        N--;
        return (T) oldFirst.item;
    }

    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }
    private class SIterator implements Iterator{
        private Node n;

        public SIterator() {
            this.n = head;
        }

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

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
}

3. 案例

3.1 括号匹配问题

问题描述：

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

例如：

"(上海)(长安)"：正确匹配;
"上海((长安))"：正确匹配;
"上海(长安(北京)(深圳)南京)"：正确匹配;
"上海(长安))"：错误匹配;
"(上海(长安)"：错误匹配;

在这里插入图片描述

代码实现

// 判断str中的括号是否匹配
public static boolean isMatch(String str){
   // 1. 创建栈对象，用来存储左括号
   Stack<String> chars = new Stack<>();

   // 2. 从左往右遍历字符串
   for (int i = 0; i < str.length(); i++) {
       String currChar = str.charAt(i) + "";
       // 3. 判断当前字符是否为左括号，如果是，则把字符放入到栈中
       if (currChar.equals("(")){
           chars.push(currChar);
       }else if (currChar.equals(")")){
           // 4. 继续判断当前字符是否是有括号，
           // 如果是，则从栈中弹出一个左括号，并判断弹出的结果是否为null
           // 如果为null证明没有匹配的左括号，如果不为null，则存在匹配的左括号
           String pop = chars.pop();
           if (pop == null){
               return false;
           }
       }
   }
   // 5. 判断栈中还有没有剩余的左括号，如果有，则证明括号不匹配
   if (chars.size() == 0){
       return true;
   }else {
       return false;
   }
}

3.2 逆波兰表达式求值问题

3.2.1 中缀表达式

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

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

3.2.2 逆波兰表达式（后缀表达式）：

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

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

3.2.3 需求：

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

在这里插入图片描述

3.2.4 实现代码

// 执行逆波兰表达式
public static int caculote(String[] notaion){
    // 1. 定义一个栈，用来存储操作数
    Stack<Integer> oprands = new Stack<>();

    // 2. 从左往右遍历逆波兰表达式，得到每一个元素
    for (int i = 0; i < notaion.length; i++) {
        String curr = notaion[i];

        Integer o1,o2,result;
        // 3. 判断当前元素是运算符还是操作数
        switch (curr){
                // 4. 运算符，从栈中弹出两个操作数，完成运算，运算玩的结果压入到栈中
            case "+":
                o1 = oprands.pop();
                o2 = oprands.pop();
                result = o2 + o1;
                oprands.push(result);
                break;
            case "-":
                o1 = oprands.pop();
                o2 = oprands.pop();
                result = o2 - o1;
                oprands.push(result);
                break;
            case "*":
                o1 = oprands.pop();
                o2 = oprands.pop();
                result = o2 * o1;
                oprands.push(result);
                break;
            case "/":
                o1 = oprands.pop();
                o2 = oprands.pop();
                result = o2 / o1;
                oprands.push(result);
                break;
            default:
                // 5. 操作数，把该操作数放入到栈中
                oprands.push(Integer.parseInt(curr));
                break;
        }
    }
    // 6. 得到栈中最后一个元素，就是逆波兰表达式的结果
    int reulst = oprands.pop();

    return reulst;
}