栈与队列不同，队列是先进先出，栈是先进后出。
栈也可以使用 数组和 链表实现。

一般的我们都会使用链表来实现，谁没事干用数组啊。

思路

比如说我们现在有一个节点 top，这个节点就类似于 我们之前讲单链表时的头节点。
只不过这里我们把它成虚拟的栈顶节点

入栈

因为栈是先进后出的结构，所以我们采取头插法比较合适。
至于头插法，我们在单链表中 进行反转链表的时候讲过了 -> 快速传送

要注意的是，如果是第一个元素的话就不必采用头插法，可以直接top.next = 新节点
但如果不是第一元素的话，就要采取头插法了
新节点 node
node.next = top.next
top.next = node

出栈

出栈的时候就更简单了，你在链表中删除第一个节点（也就是栈顶节点）就行了
top.next = top.next.next

一般的我们的栈的标配的几个方法是

  • 出栈
  • 入栈
  • 遍历
  • 获取栈顶元素，但不出栈
  • 获取栈中元素的个数

所以我们可以在 栈中加一个 int 型变量size 代表元素的个数。

代码实现

基本的节点信息：

  1. class Node {
  2.     private Object data;
  3.     private Node next;
  5.     //省略掉了 getter setter
  6. }

栈的代码：

  1. public class LinkStack {
  2.     //栈内元素个数
  3.     private int size;
  4.     //栈顶虚拟节点
  5.     private Node top = new Node("");
  7.     //判断栈是否为null
  8.     public boolean isEmpety() {
  9.         return size == 0;
  10.     }
  12.     //入栈，使用头插法
  13.     public void push(Object value) {
  14.         Node node = new Node(value);
  15.         if (isEmpety()) {
  16.             top.setNext(node);
  17.         }else {
  18.             node.setNext(top.getNext());
  19.             top.setNext(node);
  20.         }
  21.         size++;
  22.     }
  24.     //获取栈顶元素，但是不出栈
  25.     public Object top() {
  26.         if (isEmpety()) {
  27.             System.out.println("栈为空");
  28.             return null;
  29.         }
  31.         return top.getNext().getData();
  32.     }
  34.     //栈顶元素出栈
  35.     public Object pop() {
  36.         if (isEmpety()) {
  37.             return null;
  38.         }
  39.         Node node = top.getNext();
  40.         top.setNext(top.getNext().getNext());
  41.         size--;
  42.         return node.getData();
  43.     }
  45.     //遍历栈内元素，但不出栈
  46.     public void list() {
  47.         if (isEmpety()) {
  48.             System.out.println("栈空");
  49.             return;
  50.         }
  52.         Node temp = top.getNext();
  54.         while (temp != null) {
  55.             System.out.println(temp.getData());
  56.             temp = temp.getNext();
  57.         }
  58.     }
  60.     //获取栈内元素个数
  61.     public int getSize() {
  62.         return this.size;
  63.     }
  65. }

这个只是为了看起来比较好理解，但实际用的时候并不适用？每次pop值得时候都要强转太麻烦了。
于是，考虑加入泛型

带泛型的代码

  1. public class LinkStack<T> {
  2.     //栈内元素个数
  3.     private int size;
  4.     //栈顶虚拟节点
  5.     private Node<T> top = new Node("");
  7.     //判断栈是否为null
  8.     public boolean isEmpety() {
  9.         return size == 0;
  10.     }
  12.     //入栈，使用头插法
  13.     public void push(T value) {
  14.         Node<T> node = new Node(value);
  15.         if (isEmpety()) {
  16.             top.setNext(node);
  17.         }else {
  18.             node.setNext(top.getNext());
  19.             top.setNext(node);
  20.         }
  21.         size++;
  22.     }
  24.     //获取栈顶元素，但是不出栈
  25.     public T top() {
  26.         if (isEmpety()) {
  27.             System.out.println("栈为空");
  28.             return null;
  29.         }
  31.         return top.getNext().getData();
  32.     }
  34.     //栈顶元素出栈
  35.     public T pop() {
  36.         if (isEmpety()) {
  37.             return null;
  38.         }
  39.         Node<T> node = top.getNext();
  40.         top.setNext(top.getNext().getNext());
  41.         size--;
  42.         return node.getData();
  43.     }
  45.     //遍历栈内元素，但不出栈
  46.     public void list() {
  47.         if (isEmpety()) {
  48.             System.out.println("栈空");
  49.             return;
  50.         }
  52.         Node<T> temp = top.getNext();
  54.         while (temp != null) {
  55.             System.out.println(temp.getData());
  56.             temp = temp.getNext();
  57.         }
  58.     }
  60.     //获取栈内元素个数
  61.     public int getSize() {
  62.         return this.size;
  63.     }
  65. }
  67. class Node<T> {
  68.     private T data;
  69.     private Node<T> next;
  71.     public Node(T data) {
  72.         this.data = data;
  73.     }
  75.     public T getData() {
  76.         return data;
  77.     }
  79.     public void setData(T data) {
  80.         this.data = data;
  81.     }
  83.     public Node<T> getNext() {
  84.         return next;
  85.     }
  87.     public void setNext(Node<T> next) {
  88.         this.next = next;
  89.     }
  90. }

逆波兰表达式计算(后缀表达式计算)

其实私底下，用了中缀表达式来实现了，但是太过麻烦了，还要考虑优先级和括号，还不好理解。
而后缀呢，实现起来简单，但是并不符合我们人的思维需要中缀转一下后缀，而且还可以很好的处理括号问题。

(3 + 4) 5 - 6 中缀转后缀 -> 3 4 + 5 6 - ，这里我先手动转一下。至于如何转，会在下文讲解。
计算思路：
后缀表达式是从左到右进行扫描

  • 如果是数字的话，直接入栈。
  • 如果是操作符的话，从栈中pop两次得到两个数值，然后进行计算。
  1. public class PolandNotation {
  3.     public static void main(String[] args) {
  4.         //使用后缀表达式(逆波兰)来进行 表达式的计算
  5.         //为了区别 多位数，我们使用空格来将 符合和数值分割
  6.         String expr = "3 4 + 5 * 6 -";
  8.         //相比于中缀和前缀，后缀表达式更为简单，也更符合我们和计算机的思维
  9.         List<String> strings = processExpr(expr);
  10.         System.out.println(strings);
  11.         float result = getResult(strings);
  12.         System.out.println(result);
  13.     }
  15.     public static List<String> processExpr(String expr) {
  16.         String[] split = expr.split(" ");
  17.         List<String> list = new ArrayList<>();
  18.         //将分割的数组加入到 list中
  19.         Arrays.stream(split).forEach(list::add);
  20.         return list;
  21.     }
  23.     public static float getResult(List<String> expr) {
  24.         LinkStack<Float> stack = new LinkStack<>();
  25.         //开始扫描 表达式
  26.         expr.forEach(v -> {
  27.             //首先判断是数字还是字符
  28.             if (!isOperator(v)) {
  29.                 //不是符号的话直接入栈
  30.                 stack.push(Float.parseFloat(v));
  31.             }else {
  32.                 //是字符的话，从栈中pop出两个数值，然后进行计算
  33.                 float res = cal(stack.pop(), stack.pop(), v);
  34.                 //再将计算出的数值入栈
  35.                 stack.push(res);
  36.             }
  37.         });
  39.         return stack.pop();
  40.     }
  42.     public static boolean isOperator(String val) {
  43.         return  val.equals("+") ||
  44.                 val.equals("-") ||
  45.                 val.equals("*") ||
  46.                 val.equals("/");
  47.     }
  49.     public static float cal(float num1, float num2, String oper) {
  50.         float res = 0;
  51.         switch (oper) {
  52.             case "+" :
  53.                 res = num2 + num1;
  54.                 break;
  55.             case "-" :
  56.                 res = num2 - num1;
  57.                 break;
  58.             case "*" :
  59.                 res = num2 * num1;
  60.                 break;
  61.             case "/" :
  62.                 res = num2 / num1;
  63.                 break;
  64.         }
  66.         return res;
  67.     }
  69. }

中缀转后缀

中缀转后缀的时候需要有两个栈，这里称为 s1 , s2
先对 (3 + 4) * 5 - 6 进行扫描

如果是数字的话，直接压入 s2

如果是字符的话
1.1 如果栈中为空，或者栈顶元素位 ( 那么直接压入 s1。
1.2 如果栈不为空，栈顶元素位 ) ，那么从s1 pop 一个运算符 压入 s2，直到 pop出来的运算符位 ( 为止，此时消去了 一对 ()
1.3 如果当前字符 优先级高于 栈顶元素的话 直接入 s1，否则跳到1.4
1.4 当前运算符的优先级 小于等于 栈顶元素。 s1 pop 出运算符到 s2中，直到当前运算符高于 栈顶运算符或者栈为空的情况，新的运算符入栈。
如果遍历完毕表达式
那么将 s1 中的所有元素 依次pop出，然后压入到 s2 中，此时 s2 从栈顶到栈底，就是 后缀表达式的倒序。

看一下例子：

当操作符是 ( + ) -
s1 ( —> s1 ( + —> s1 —> s1 —> s1 - —> s1
s2 3 s2 3 4 s2 3 4 + s2 3 4 + 5 s2 3 4 + 5 6 s2 3 4 + 5 6 -

加入 中缀转后缀后，代码实现

  1. package cn.edu.zzuli.stack;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.Collection;
  6. import java.util.List;
  7. import java.util.regex.PatternSyntaxException;
  9. public class PolandNotation {
  11.     public static void main(String[] args) {
  12.         //使用后缀表达式(逆波兰)来进行 表达式的计算
  13.         //为了区别 多位数，我们使用空格来将 符合和数值分割
  14.         String nifix = "1 + ( ( 2 + 3 ) * 4 ) - 5";
  15.         //String expr = "3 4 + 5 * 6 -";
  16.         List<String> expr = nifixToPostfix(processExpr(nifix));
  17.         //System.out.println(expr);
  18.         float result = getResult(expr);
  19.         System.out.println(result);
  20.     }
  22.     public static List<String> nifixToPostfix(List<String> nifix) {
  23.         //存放符号
  24.         LinkStack<String> stack = new LinkStack<>();
  25.         //用来代替栈s2，存放结果,因为我们的 s2栈并没有pop操作，所以可以代替。
  26.         List<String> postfix = new ArrayList<>();
  27.         nifix.forEach(v -> {
  28.             //判断是符号还是数字
  29.             if (isOperator(v)) {
  30.                 //如果栈为空 或者 栈顶为 (
  31.                 if (stack.isEmpety() || stack.top().equals("(") || v.equals("(")) {
  32.                     stack.push(v);
  33.                 }
  34.                 else if (v.equals(")")) {
  35.                     //依次弹出
  36.                     while (!stack.top().equals("(")) {
  37.                         postfix.add(stack.pop());
  38.                     }
  39.                     //弹出 (
  40.                     stack.pop();
  41.                 }
  42.                 else{
  43.                     //判断优先级 <= 得情况
  44.                     while (!stack.isEmpety() && priority(v) <= priority(stack.top())) {
  45.                         postfix.add(stack.pop());
  46.                     }
  47.                     //此时栈顶有元素的话，已经比当前运算符的优先级高了
  48.                     stack.push(v);
  49.                 }
  50.             }else {
  51.                 //数字直接入栈
  52.                 postfix.add(v);
  53.             }
  54.         });
  56.         while (!stack.isEmpety()) {
  57.             postfix.add(stack.pop());
  58.         }
  60.         return postfix;
  61.     }
  63.     public static List<String> processExpr(String expr) {
  64.         String[] split = expr.split(" ");
  65.         List<String> list = new ArrayList<>();
  66.         //将分割的数组加入到 list中
  67.         Arrays.stream(split).forEach(list::add);
  68.         return list;
  69.     }
  71.     public static float getResult(List<String> expr) {
  72.         LinkStack<Float> stack = new LinkStack<>();
  73.         //开始扫描 表达式
  74.         expr.forEach(v -> {
  75.             //首先判断是数字还是字符
  76.             if (!isOperator(v)) {
  77.                 //不是符号的话直接入栈
  78.                 stack.push(Float.parseFloat(v));
  79.             }else {
  80.                 //是字符的话，从栈中pop出两个数值，然后进行计算
  81.                 float res = cal(stack.pop(), stack.pop(), v);
  82.                 //再将计算出的数值入栈
  83.                 stack.push(res);
  84.             }
  85.         });
  87.         return stack.pop();
  88.     }
  90.     public static int priority(String oper) {
  91.         if (oper.equals("*") || oper.equals("/")) {
  92.             return 10;
  93.         } else if (oper.equals("+") || oper.equals("-")) {
  94.             return 5;
  95.         }
  97.         return -1;
  98.     }
  99.     public static boolean isOperator(String val) {
  100.         return  val.equals("+") ||
  101.                 val.equals("-") ||
  102.                 val.equals("*") ||
  103.                 val.equals("/") ||
  104.                 val.equals("(") ||
  105.                 val.equals(")");
  106.     }
  108.     public static float cal(float num1, float num2, String oper) {
  109.         float res = 0;
  110.         switch (oper) {
  111.             case "+" :
  112.                 res = num2 + num1;
  113.                 break;
  114.             case "-" :
  115.                 res = num2 - num1;
  116.                 break;
  117.             case "*" :
  118.                 res = num2 * num1;
  119.                 break;
  120.             case "/" :
  121.                 res = num2 / num1;
  122.                 break;
  123.         }
  125.         return res;
  126.     }
  128. }