时间:2021-05-19
栈是限制插入和删除只能在一个位置上进行的 List,该位置是 List 的末端,叫做栈的顶(top),对于栈的基本操作有 push 和 pop,前者是插入,后者是删除。
栈也是 FIFO 表。
栈的实现有两种,一种是使用数组,一种是使用链表。
public class MyArrayStack<E> { private ArrayList<E> list = new ArrayList<>(); public void push(E e) { list.add(e); } public E pop() { return list.remove(list.size() - 1); } public E peek() { return list.get(list.size() - 1); } public boolean isEmpty() { return list.size() == 0; }}public class MyLinkStack<E> { LinkedList<E> list = new LinkedList<>(); public void push(E e) { list.addLast(e); } public E pop() { return list.removeLast(); } public E peek() { return list.getLast(); } public boolean isEmpty() { return list.size() == 0; }}栈的应用
平衡符号
给定一串代码,我们检查这段代码当中的括号是否符合语法。
例如:[{()}] 这样是合法的,但是 [{]}() 就是不合法的。
如下是测试代码:
public class BalanceSymbol { public boolean isBalance(String string) { MyArrayStack<Character> stack = new MyArrayStack<>(); char[] array = string.toCharArray(); for (char ch : array) { if ("{[(".indexOf(ch) >= 0) { stack.push(ch); } else if ("}])".indexOf(ch) >= 0) { if (isMatching(stack.peek(), ch)) { stack.pop(); } } } return stack.isEmpty(); } private boolean isMatching(char peek, char ch) { if ((peek == '{' && ch == '}') || (peek == '[' && ch == ']') || (peek == '(' && ch == ')')) { return true; } return false; } public static void main(String[] args) { BalanceSymbol symbol = new BalanceSymbol(); String string = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol();}"; String string2 = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol([);}]"; System.out.println(symbol.isBalance(string)); System.out.println(symbol.isBalance(string2)); }}后缀表达式
例如一个如下输入,算出相应的结果,
3 + 2 + 3 * 2 = ?
这个在计算顺序上不同会产生不同的结果,如果从左到右计算结果是 16,如果按照数学优先级计算结果是 11。
如果把上述的中缀表达式转换成后缀表达式:
3 2 + 3 2 * +
如果使用后缀表达式来计算这个表达式的值就会非常简单,只需要使用一个栈。
每当遇到数字的时候,把数字入栈。
每当遇到操作符,弹出2个元素根据操作符计算后,入栈。
最终弹出栈的唯一元素就是计算结果。
/** * 简化版本,每个操作数只一位,并且假设字符串合法 */public class PostfixExpression { public static int calculate(String string) { MyArrayStack<String> stack = new MyArrayStack<>(); char[] arr = string.toCharArray(); for (char ch : arr) { if ("0123456789".indexOf(ch) >= 0) { stack.push(ch + ""); } else if ("+-*/".indexOf(ch) >= 0) { int a = Integer.parseInt(stack.pop()); int b = Integer.parseInt(stack.pop()); if (ch == '+') { stack.push((a + b) + ""); } else if (ch == '-') { stack.push((a - b) + ""); } else if (ch == '*') { stack.push((a * b) + ""); } else if (ch == '/') { stack.push((a / b) + ""); } } } return Integer.parseInt(stack.peek()); } public static void main(String[] args) { System.out.println(calculate("32+32*+")); }}中缀表达式转换成后缀表达式
假设只运行 +,-,*,/,() 这几种表达式。并且表达式合法。
a + b * c - (d * e + f) / g 转换后的后缀表达式如下:
a b c * + d e * f + g / -
使用栈中缀转后缀步骤如下:
通过此文,希望大家对Java stack 的知识掌握,谢谢大家对本站的支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
java仿Servlet生成验证码实例详解实现原理:使用BufferedImage对象的Graphics来进行绘制,然后输出成一张图片进行保存实现代码及详解:p
Javascript实现计算器:系列文章:JS实现计算器详解及实例代码(一)Javascript实现计算器时间功能详解及实例(二)小型JavaScript计算器
java实现单链表逆转详解实例代码:classNode{Nodenext;Stringname;publicNode(Stringname){this.name
Javascript计算器:系列文章:JS实现计算器详解及实例代码(一)Javascript实现计算器时间功能详解及实例(二)Javascript计算器->添加
java实现可安装的exe程序实例详解通过编写Java代码,实现可安装的exe文件的一般思路:1、在eclipse中创建java项目,然后编写Java代码,将编