（JAVA）浅尝关于 “栈” 数据结构

1. 栈的概述：

1.1 生活中的栈

存储货物或供旅客住宿的地方，可引申为仓库、中转站。例如酒店，在古时候叫客栈，是供旅客休息的地方，旅客可以进客栈休息，休息完毕后就离开客栈

1.2计算机中的栈

• 将生活中的栈的概念引入到计算机汇总，就是供数据休息的地方，它是一种数据结构，数据既可以进入到栈中，又可以从栈中出去。
• 栈是一种基于先进后出（FILO）的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。
  • 它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）
• 我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈

2. 栈的实现

2.1 栈API设计

类名	Stack
构造方法	Stack()：创建Stack对象
成员方法	1. public boolean isEmpty()：判断栈是否为空，是返回true，否返回false 2. public int size()：获取栈中元素的个数 3. public T pop()：弹出栈元素 4. public void push(T t)：向栈中压入元素t
成员变量	1. private Node head：记录首节点 2. private int N：当前栈的元素个数
成员内部类	private class Node：节点类

2.2 代码实现

package com.renexdemo.linear;import java.util.Iterator;public class Stack<T> implements Iterable<T> {private Node head;private int N;// 节点类private static class Node<T>{public T item;// 存储元素public Node next;// 指向下一个节点public Node(T item, Node next) {this.item = item;this.next = next;}}// 初始化栈public Stack() {this.head = new Node(null,null);this.N = 0;}// 判断栈是否为空public boolean isEmpty(){return N == 0;}// 获得栈中的数量public int size(){return N;}// 压栈public void push(T t){// 找到首节点指向的第一个节点Node oldNode = head.next;// 创建新节点Node<T> newNode = new Node<>(t, null);// 让首节点指向新节点head.next = newNode;// 让新节点指向原来的第一个节点newNode.next = oldNode;// 元素个数+1N++;}// 弹栈public T pop(){// 找到首节点指向的第一个节点Node oldFirst = head.next;if (oldFirst == null){return null;}// 让首节点指向原来第一个节点的下一个节点head.next=oldFirst.next;// 元素个数-1N--;return (T) oldFirst.item;}@Overridepublic Iterator<T> iterator() {return new SIterator();}private class SIterator implements Iterator{private Node n;public SIterator() {this.n = head;}@Overridepublic boolean hasNext() {return n.next != null;}@Overridepublic Object next() {n = n.next;return n.item;}}
}

3. 案例

3.1 括号匹配问题

问题描述：

给定一个字符串，里边可能包含"()"小括号和其他字符，请编写程序检查该字符串中的小括号是否成对出现

例如：

"(上海)(长安)"：正确匹配;
"上海((长安))"：正确匹配;
"上海(长安(北京)(深圳)南京)"：正确匹配;
"上海(长安))"：错误匹配;
"(上海(长安)"：错误匹配;

代码实现

// 判断str中的括号是否匹配
public static boolean isMatch(String str){// 1. 创建栈对象，用来存储左括号Stack<String> chars = new Stack<>();// 2. 从左往右遍历字符串for (int i = 0; i < str.length(); i++) {String currChar = str.charAt(i) + "";// 3. 判断当前字符是否为左括号，如果是，则把字符放入到栈中if (currChar.equals("(")){chars.push(currChar);}else if (currChar.equals(")")){// 4. 继续判断当前字符是否是有括号，// 如果是，则从栈中弹出一个左括号，并判断弹出的结果是否为null// 如果为null证明没有匹配的左括号，如果不为null，则存在匹配的左括号String pop = chars.pop();if (pop == null){return false;}}}// 5. 判断栈中还有没有剩余的左括号，如果有，则证明括号不匹配if (chars.size() == 0){return true;}else {return false;}
}

3.2 逆波兰表达式求值问题

3.2.1 中缀表达式

​ 中缀表达式就是我们平常生活中使用的表达式，例如：1+3*2,2,2-(1+3)等等，中缀表达式的特点是：二元运算符总是置于两个操作数中间。

​ 中缀表达式是人们最喜欢的表达式方式，因为简单、易懂。但是对于计算机来说就不是这样了，因为中缀表达式的运算顺序不具有规律性，不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做大量的优先级相关操作

3.2.2 逆波兰表达式（后缀表达式）：

​ 逆波兰表达式是 波兰逻辑学家j · 卢卡西维兹（J · Lukasewicz） 于1929年首先提出的一种表达式的表示方法，后缀表达式的特点：运算符总是放在跟它相关的操作数之后

中缀表达式	逆波兰表达式
a+b	ab+
a+(b-c)	abc-+
a+(b-c)*d	abc-d*+
a*(b-c)+d	abc-*d+

3.2.3 需求：

给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式，求出该逆波兰表达式的结果

3.2.4 实现代码

// 执行逆波兰表达式
public static int caculote(String[] notaion){// 1. 定义一个栈，用来存储操作数Stack<Integer> oprands = new Stack<>();// 2. 从左往右遍历逆波兰表达式，得到每一个元素for (int i = 0; i < notaion.length; i++) {String curr = notaion[i];Integer o1,o2,result;// 3. 判断当前元素是运算符还是操作数switch (curr){// 4. 运算符，从栈中弹出两个操作数，完成运算，运算玩的结果压入到栈中case "+":o1 = oprands.pop();o2 = oprands.pop();result = o2 + o1;oprands.push(result);break;case "-":o1 = oprands.pop();o2 = oprands.pop();result = o2 - o1;oprands.push(result);break;case "*":o1 = oprands.pop();o2 = oprands.pop();result = o2 * o1;oprands.push(result);break;case "/":o1 = oprands.pop();o2 = oprands.pop();result = o2 / o1;oprands.push(result);break;default:// 5. 操作数，把该操作数放入到栈中oprands.push(Integer.parseInt(curr));break;}}// 6. 得到栈中最后一个元素，就是逆波兰表达式的结果int reulst = oprands.pop();return reulst;
}

3.2.4.1 逻辑问题

当做进行运算符计算时，由于栈是先进后出类型。

所以弹出两个元素，不能是第一个弹出的元素对第二个元素进行运算。

例如：{17,16}

• 17先压栈，然后16

• 那么在弹栈后，16为第一个元素，17为第二个元素，当作 / 或 - 运算时就不符合本身的运算逻辑了
  意思是原来操作逻辑是17-16那么经过弹栈后，两者互调了位置变成了16-17。这两个结果是截然不同的

4. 总结：

常见，常用的数据结构，同样也比较好实现，可以在许多的业务场景中见到类似的模式，分析这种结构后可以提高一定的见解。