这里有新鲜出炉的Java设计模式,程序狗速度看过来!
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台(即JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
这篇文章主要介绍了java 实现 stack详解的相关资料,需要的朋友可以参考下
栈是限制插入和删除只能在一个位置上进行的 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 / -
使用栈中缀转后缀步骤如下:
- import java.util.HashMap;
- import java.util.Map;
- public class ExpressionSwitch {
- private static Map<Character, Integer> map = new HashMap<Character, Integer>();
- static {
- map.put('+', 0);
- map.put('-', 1);
- map.put('*', 2);
- map.put('/', 3);
- map.put('(', 4);
- }
- private static char[][] priority = {
- // 当前操作符
- // + - * / (
- /* 栈 + */{ '>', '>', '<', '<', '<'},
- /* 顶 - */{ '>', '>', '<', '<', '<'},
- /* 操 * */{ '>', '>', '>', '>', '<'},
- /* 作 / */{ '>', '>', '>', '>', '<'},
- /* 符 ( */{ '<', '<', '<', '<', '<'},
- };
- public static String switch1(String string) {
- StringBuilder builder = new StringBuilder();
- char[] arr = string.toCharArray();
- MyArrayStack<Character> stack = new MyArrayStack<>();
- for (char ch : arr) {
- if ("0123456789abcdefghijklmnopqrstuvwxyz".indexOf(ch) >= 0) {
- builder.append(ch);
- } else if ('(' == ch) {
- stack.push(ch);
- } else if (')' == ch) {
- while (true && !stack.isEmpty()) {
- char tmp = stack.pop();
- if (tmp == '(') {
- break;
- } else {
- builder.append(tmp);
- }
- }
- } else {
- while (true) {
- if (stack.isEmpty()) {
- stack.push(ch);
- break;
- }
- char tmp = stack.peek();
- if (isPriorityHigh(tmp, ch)) {
- builder.append(stack.pop());
- } else {
- stack.push(ch);
- break;
- }
- }
- }
- }
- while(!stack.isEmpty()) {
- builder.append(stack.pop());
- }
- return builder.toString();
- }
- private static boolean isPriorityHigh(char tmp, char ch) {
- return priority[map.get(tmp)][map.get(ch)] == '>';
- }
- public static void main(String[] args) {
- System.out.println(switch1("a+b*c-(d*e+f)/g"));
- }
- }
来源: http://www.phperz.com/article/17/1116/359875.html