java 实现 stack详解及实例代码

java 实现 stack详解及实例代码

栈是限制插入和删除只能在一个位置上进行的 List，该位置是 List 的末端，叫做栈的顶(top)，对于栈的基本操作有 push 和 pop，前者是插入，后者是删除。

栈也是 FIFO 表。

栈的实现有两种，一种是使用数组，一种是使用链表。

public class MyArrayStack {

private ArrayList 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 {

LinkedList 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(SXMyAkEtring string) {

MyArrayStack 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 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 map = new HashMap();

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 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 的知识掌握，谢谢大家对本站的支持！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。