六、栈、栈的相关问题

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

前言

一、栈

1.栈概述

2.栈的实现

2.1 栈的API

2.2 栈的实现

二、栈的括号匹配问题

1.问题描述

2.代码实现

三、逆波兰表达式求值问题

1.问题描述

2.代码

总结

---

前言

提示：这里可以添加本文要记录的大概内容：

自学JAVA数据结构笔记，跟学视频为：黑马程序员Java数据结构与java算法全套教程，数据结构+算法教程全资料发布，包含154张java数据结构图_哔哩哔哩_bilibili

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、栈

1.栈概述

栈是一种基于先进后出(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:当前栈的元素个数

2.2 栈的实现

package List;import java.util.Iterator;/*
*       使用链表实现栈
* */
public class Stack <T> implements Iterable<T>{private Node head;private int N;//结点类private class Node{private T item;private 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;}//把t元素压入栈public void push(T t){//第一个结点Node first = head.next;//创建新结点//由于栈的特点是先入后出，使用新压入的结点为链表的第一个结点Node newNode = new Node(t,first);head.next = newNode;N ++;}//出栈public T pop(){//出栈结点Node curr = head.next;if(curr == null){return null;}//头结点的下一个结点指向要删除结点的下一个结点‘head.next = curr.next;N --;return curr.item;}//实现迭代器@Overridepublic Iterator<T> iterator() {return new STiterator();}private class STiterator implements Iterator{private Node curr;public STiterator(){this.curr = head;}@Overridepublic boolean hasNext(){return curr.next != null;}@Overridepublic Object next() {curr = curr.next;return curr.item;}}}

二、栈的括号匹配问题

1.问题描述

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

例如：

        "(上海)(长安)"：正确匹配

        "上海((长安))"：正确匹配

        "上海(长安(北京)(深圳)南京)":正确匹配

        "上海(长安))"：错误匹配

        "((上海)长安"：错误匹配

2.代码实现

package Stack;import java.util.Scanner;public class BracketsMatch {public static void main(String[] args) {//创建字符串Scanner input = new Scanner(System.in);String str = "上海(长安))";//判断是否是有效括号boolean match = isMatch(str);if(match){System.out.println("正确匹配");}else{System.out.println("错误匹配");}}public static boolean isMatch(String str){//创建栈对象//1.创建一个栈用来存储左括号Stack<String> chars = new Stack<String>();//2.从左往右遍历字符串，拿到每一个字符for (int i = 0; i < str.length(); i++) {String curr = str.charAt(i) + "";//3.判断该字符是不是左括号，如果是，放入栈中存储if (curr.equals("(")) {chars.push(curr);} else if (curr.equals(")")) {//4.判断该字符是不是右括号，如果不是，继续下一次循环//5.如果该字符是右括号，则从栈中弹出一个元素t；String res = chars.pop();//6.判断元素t是否为null，如果不是，则证明有对应的左括号，如果不是，则证明没有对应的左括号if (res == null) {return false;}}}//7.循环结束后，判断栈中还有没有剩余的左括号，如果有，则不匹配，如果没有，则匹配return chars.size() == 0;}
}

---

三、逆波兰表达式求值问题

1.问题描述

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

中缀表达式：

中缀表达式就是我们平常生活中使用的表达式，例如：

1+3*2,2-(1+3)等等，

中缀表达式的特点是：二元运算符总 是置于两个操作数中间。

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

逆波兰表达式(后缀表达式)：

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

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

2.代码

package Stack;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) {//1.创建一个栈对象oprands存储操作数Stack<Integer> oprands = new Stack<Integer>();//2.从左往右遍历逆波兰表达式，得到每一个字符串for (String curr : notaion) {//3.判断该字符串是不是运算符，如果不是，把该该操作数压入oprands栈中Integer o1;Integer o2;Integer result;switch (curr) {case "+"://4.如果是运算符，则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();//5.使用该运算符计算o1和o2，得到结果resultresult = o2 + o1;//6.把该结果压入oprands栈中oprands.push(result);break;case "-"://4.如果是运算符，则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();//5.使用该运算符计算o1和o2，得到结果resultresult = o2 - o1;//6.把该结果压入oprands栈中oprands.push(result);break;case "*"://4.如果是运算符，则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();//5.使用该运算符计算o1和o2，得到结果resultresult = o2 * o1;//6.把该结果压入oprands栈中oprands.push(result);break;case "/"://4.如果是运算符，则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();//5.使用该运算符计算o1和o2，得到结果resultresult = o2 / o1;//6.把该结果压入oprands栈中oprands.push(result);break;default:oprands.push(Integer.parseInt(curr));break;}}//7.遍历结束后，拿出栈中最终的结果返回Integer result = oprands.pop();return result;}
}

总结

提示：这里对文章进行总结：