目录
- 栈是一种什么样的数据结构？
- 栈的实现
-
- 栈的应用
-
<1> 基于它的LIFO策略，可以逆序排列
-
<2> 模拟计算机实现简单的算术表达式求值
1. 栈是一种什么样的数据结构？
栈(下压栈)是一种基于后进先出(LIFO:last-in,first-out)策略的集合类型。
stack(栈)
现实生活中我们可以把栈想象成厨房里摞盘子的架子，后放进去的盘子在最上层，先取用，如下图：
stack(栈)_盘子
2. 栈的实现
使用数组实现栈
数组实现栈
JDK中栈的实现类为：java.util.Stack.java，继承了Vector，支持泛型，内部实现是一个对象数组，默认的初始大小为10。
Stack类：
public class Stack<E> extends Vector<E>
内部实现：
protected Object[] elementData;
对于Stack类的操作也比较简单，支持如下操作：
## 1.压入操作
## 将元素item压入栈顶，返回压入的item元素
## 如果现有数组满了，则进行扩容，数组扩大为原来的两倍
public E push(E item)
## 2.弹出操作
## 将栈顶的元素取出，转成E对象，并返回
## 底层Object[]数组原栈顶位置的对象引用置空
## 整个操作都是线程安全的，两个线程同时执行的话，其中一个会被阻塞
public synchronized E pop()
## 3.查看栈顶的元素（peek翻译过来是‘偷看’的意思）
## 只返回栈顶的元素，但栈顶元素不弹出栈
## 操作是线程安全的
public synchronized E peek()
## 4.判断栈是否为空
public boolean empty()
## 5.查询栈中指定的元素
## 查询元素o，并返回元素o在栈中的位置（栈顶从1开始向下，到元素o的位置）
## 栈中没有元素o时，则返回-1
## 操作是线程安全的
public synchronized int search(Object o)
对于Stack类的search操作，图示举例：
stack_search操作
3. 栈的应用
栈可以用来做什么用呢？
<1> 基于它的LIFO策略，可以逆序排列。
例如：利用栈的结构，可以将给定的字符串逆序输出。
先将字符串每个字符压入栈中，然后再将栈中字符依次弹出，即可得到原字符串的逆序。
代码实现如下：
/**
* 利用栈结构将给定的字符串逆序输出
* @param value
* @return
*/
public static String reverse(String value) {
if (value == null || "".equals(value.trim())) {
return value;
}
Stack<Character> stack = new Stack<>();
for (char c : value.toCharArray()) {
stack.push(c);
}
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
result.append(stack.pop());
}
return result.toString();
}
测试：
System.out.println(StackDemo.reverse("1,2,3,4,5,6"));
System.out.println(StackDemo.reverse("22 23 24 25 ;"));
System.out.println(StackDemo.reverse("HH_oo_20190010*/$${}ppXX@##&"));
输出：
6,5,4,3,2,1
; 52 42 32 22
&##@XXpp}{$$/*01009102_oo_HH
⚠️ 注意：逆序输出不能使用JDK中Stack类的foreach, while + iterator迭代遍历栈中元素，一定要用pop()操作。
原因：JDK中Stack类的迭代器，遍历栈中元素，都是从底层对象数组的索引为0处开始，即栈底，而不是栈顶，所以输出的还是原来的顺序。
举例：
Stack<Integer> stack = new Stack<>();
int[] values = {1,2,3,4,5};
for (int v : values) {
stack.push(v);
}
1.直接输出栈本身：System.out.println(stack);
结果还是原序：[1, 2, 3, 4, 5]
2.foreach遍历，输出的也是原序：1 2 3 4 5
for (int s : stack) {
System.out.println(s);
}
3.while + iterator遍历，输出的也是原序：1 2 3 4 5
Iterator iterator = stack.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
<2> 模拟计算机实现简单的算术表达式求值
使用两个栈实现，一个保存运算符，一个保存操作数：
运算符栈+操作数栈
处理过程：
- 将操作数压入操作数栈
- 将运算符压入运算符栈（忽略左括号）
- 遇到右括号时，弹出一个运算符，弹出所需数量的操作数，进行运算，并将运算的结果压入操作数栈中。
代码实现如下：
/**
* @author : rangdandanfei
* @description : 用两个栈(一个保存运算符，一个保存操作数)实现简单的算术表达式求值
*/
public class CalculateDemo {
public static void main(String[] args) {
Stack<String> ops = new Stack<>();
Stack<Double> vals = new Stack<>();
Scanner scanner = new Scanner(System.in);
String s;
while ((s = scanner.nextLine()) != null && !"".equals(s = s.trim())) {
if (s.equals("(")) {
// 如果字符为"("，则忽略
} else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("sqrt")) {
// 压入运算符
ops.push(s);
} else if (s.equals(")")) {
// 如果字符为")"，弹出运算符和所需操作数，进行计算，计算结果压入栈中
String op = ops.pop();
double v = vals.pop();
if (op.equals("+")) {
v = vals.pop() + v;
} else if (op.equals("-")) {
v = vals.pop() - v;
} else if (op.equals("*")) {
v = vals.pop() * v;
} else if (op.equals("/")) {
v = vals.pop() / v;
} else if (op.equals("sqrt")) {
v = Math.sqrt(v);
}
vals.push(v);
} else {
// 压入操作数
vals.push(Double.parseDouble(s));
}
}
System.out.println(vals.pop());
}
}
测试输入：(1 + ((2 + 3) * (4 * 5)))
输出：101.0
网友评论