知识产权教育网站建设方案,四川关于工程建设网站,大连公司排名,网业升级坊问提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 目录 前言 一、栈 1.栈概述 2.栈的实现 2.1 栈的API 2.2 栈的实现 二、栈的括号匹配问题 1.问题描述 2.代码实现 三、逆波兰表达式求值问题 1.问题描述 2.代码 总结 前言
提… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 目录 前言 一、栈 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 IterableT{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 IteratorT 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.创建一个栈用来存储左括号StackString chars new StackString();//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.如果该字符是右括号则从栈中弹出一个元素tString res chars.pop();//6.判断元素t是否为null如果不是则证明有对应的左括号如果不是则证明没有对应的左括号if (res null) {return false;}}}//7.循环结束后判断栈中还有没有剩余的左括号如果有则不匹配如果没有则匹配return chars.size() 0;}
}三、逆波兰表达式求值问题
1.问题描述
逆波兰表达式求值问题是我们计算机中经常遇到的一类问题要研究明白这个问题首先我们得搞清楚什么是逆波 兰表达式要搞清楚逆波兰表达式我们得从中缀表达式说起。
中缀表达式
中缀表达式就是我们平常生活中使用的表达式例如
13*2,2-(13)等等
中缀表达式的特点是二元运算符总 是置于两个操作数中间。
中缀表达式是人们最喜欢的表达式方式因为简单易懂。但是对于计算机来说就不是这样了因为中缀表达式的 运算顺序不具有规律性。不同的运算符具有不同的优先级如果计算机执行中缀表达式需要解析表达式语义做大量的优先级相关操作。
逆波兰表达式(后缀表达式)
逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法后缀表 达式的特点运算符总是放在跟它相关的操作数之后。
中缀表达式逆波兰表达式ababa(b-c)abc-a(b-c)*dabc-d*a*(b-c)dabc-*d2.代码
package Stack;public class ReversePolishNotation {public static void main(String[] args) {//中缀表达式3*17-1518/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存储操作数StackInteger oprands new StackInteger();//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;}
}
总结
提示这里对文章进行总结
