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 / -

使用栈中缀转后缀步骤如下：

1. 当读到操作数立即把它输出
2. 如果遇到操作符入栈，如果遇到的左括号也放到栈中
3. 如果遇到右括号，就开始弹出栈元素，直到遇到对应的左括号，左括号只弹出不输出。
4. 如果遇到其他符号，那么从栈中弹出栈元素知道发现优先级更低的元素为止。

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"));
 }
}
 

通过此文，希望大家对java stack 的知识掌握，谢谢大家对本站的支持！