基础数据结构-栈 - 图1

1. 什么是栈？

1.1 栈的基本概念

栈是一种特殊的线性表结构，它具有后进先出/先进后出的特性（Last In First Out/First In Last Out），栈只能从一端进行数据元素的插入和删除操作，插入元素可称之为压栈、入栈、进栈，出栈入栈的一端被称为栈顶，另一端为栈底。
基础数据结构-栈 - 图2

1.2 栈的特点

是一种特殊的线性表。
先进后出/后进先出。
只能从一端删除元素。
2. 栈的实现
因为栈是一种特殊的线性表结构，所以从线性表就可以联想到数组与链表，而栈也可以说成是一种特殊的数组或链表，因为栈可以基于数组、链表实现。
2.1 基于数组实现栈
基于数组的方式实现栈以数组的头部为栈底，以从数组的头部到尾部为栈的生长方向。
```java package com.muzili.stack;

@author: muzili(李敷斌)
@date: 2021/7/20
@version: v0.0.1
@description: 基于数组实现栈 */ public class ArrayStack implements Stack{

/**
- 保存数组的栈 */ private T[] stackArr;
  
  /**
- 容量 */ private int capcity = 20;
  
  /**
- 栈实际大小 */ private int size = 0;
  
  public ArrayStack() { stackArr = (T[]) new Object[capcity]; }
  
  public ArrayStack(int capcity) { this.capcity = capcity; stackArr = (T[]) new Object[capcity]; }
  
  /**
- 入栈 *
- @param item */ public void push(T item) { //判断大小是否足够如果不够进行扩容 judgeSize(); stackArr[size++] = item; }
  
  /**
- 判断大小 */ private void judgeSize() {
  
  if (size >= capcity){
```
 //如果实际大小+1大于或等于容量大小 则需要进行扩容
 capcity = capcity * 2;
 resize(capcity);
```
  }else if (size > 0 && size > 20 && size <= capcity / 2){
```
 capcity = capcity / 2;
 resize(capcity);
```
  }
  
  }
  
  /**
- 改变数组大小
- @param capcity */ public void resize(int capcity){
  
  T[] temp = (T[]) new Object[capcity]; int count = capcity > this.capcity ? this.capcity:capcity; for (int i = 0; i < count; i++) {
```
 temp[i] = stackArr[i];
```
  } stackArr = temp; }
  
  /**
- 出栈 *
- @return */ public T pop() {
  
  if (isEmpty()){
```
 return null;
```
  } T item = stackArr[—size]; stackArr[size] = null; judgeSize(); return item; }
  
  /**
- 是否为空 *
- @return */ public boolean isEmpty() { return size == 0; }

}

<a name="Di4LA"></a>
## 2.2 基于链表实现栈
基于链表的方式实现栈，以链表表头为栈低，入栈的元素插入链表尾部，通过链表实现便于元素的插入和删除。<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/21857252/1626750238886-0d038391-a81e-4412-a3a4-c3f0a711926b.png#align=left&display=inline&height=69&margin=%5Bobject%20Object%5D&name=image.png&originHeight=69&originWidth=319&size=3496&status=done&style=none&width=319)
```java
package com.muzili.stack;
import com.muzili.list.LinkedList;
/**
 * 
 * @author: muzili(李敷斌)
 * @date: 2021/7/20
 * @version: v0.0.1
 * @description: 基于LinkedList实现栈
 */ 
public class LinkedListStack<T> implements Stack<T>{
    /**
     * 保存数据的链表
     */
    private LinkedList<T> itemList = new LinkedList<T>();
    /**
     * 入栈
     *
     * @param item
     */
    public void push(T item) {
        itemList.addLast(item);
    }
    /**
     * 出栈
     *
     * @return
     */
    public T pop() {
        T data = itemList.getLast().getData();
        itemList.removeLast();
        return data;
    }
    /**
     * 是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return itemList.getSize() == 0;
    }
}

2.3 数组实现VS链表实现

区别：

链表实现起来更加简单。
数组需要有扩容操作，否则可能会导致栈溢出。
链表有天然的自动扩容的优势。

3. 栈的使用场景

函数调用
- 比如Java语言中函数调用，后调用的方法会先执行完毕，这就是一个典型的栈结构。
数学表达式计算
- https://www.cnblogs.com/leon0812/articles/1211638.html
- 比如这样一个表达式2-3*5/6-2，计算机无法一步识别出计算的先后顺序，而通过栈就可以解决这个问题，使用两个栈，一个栈存数值，一个栈存计算符号，如果压入符号时，当前待压入的符号优先级大于栈顶符号则直接入栈，否则出栈。 ```java package com.muzili.stack;

import java.math.BigDecimal; import java.util.Arrays;

/**

数学表达式计算 *
使用两个栈实现
一个栈存储数值一个栈存储符号 *
规则数值入栈如果入栈的时符号与栈顶的符号比对如果栈顶的符号优先级低于当前符号将符号压入栈
如果栈顶符号优先级高于或等于待入栈符号则栈顶符号出栈取两个数值进行计算然后重复以上步骤 *
step 1 如果入栈的是一个符号与栈顶进行对比
step 2 如果待入栈符号优先级高于栈顶符号直接入栈，否则栈顶元素出栈然后再取出两个数值进行运算运算结果再入栈
step 3 重复上述步骤 *
符号优先级
( -1
- - 0
- / 1
) 2 / -1（当比较的对象是(为-1）
如 2+35+6+(1+53)+1 *
tip：把 (,)当做特殊的运算符相邻的两个可以抵消 *
1. 2入栈 +号入栈，因为符号栈栈顶为null直接入栈
1. 3入栈 与栈顶元素比较，比+号的优先级高，入栈
1. 5入栈 +与栈顶符号比较 +比的优先级小，*出栈，数值出栈5 3,
1. 进行运算，运算结果压入数值栈3 * 5 = 15
1. +号在与栈顶符号+对比，结果与栈顶符号相等，优先出现的符号先计算，出栈+号数值出栈2 15
1. 2 + 15 = 17，运算结果入栈，此时栈顶为null +号直接入栈符号栈
1. 6入栈，符号+ 与栈顶符号+比较两个符号优先级相等栈顶符号+出栈数值栈 17,6出栈
1. 17 + 6 = 23运算结果入栈，+号直接入栈
1. 符号 (入栈，数值1入栈
1. 符号+与栈顶符号(比较栈顶符号(优先级小于+，+号入栈，数值5入栈
1. 符号与栈顶符号+比较栈顶符号优先级小 符号*入栈，数值3入栈
1. 符号)与栈顶符号比较栈顶符号优先级高于) 出栈符号 出栈数值3 5
1. 5 * 3 = 15运算结果入栈，符号)与栈顶符号比较栈顶符号优先级高于)，栈顶符号出栈 + 数值出栈 15 3
1. 1 + 15 = 16运算结果入栈，符号)与栈顶符号比较栈顶符号优先级与符号)相等，栈顶符号出栈因为是特殊符号所以不取数值
1. ()相互抵消，+号与栈顶符号+比较大小相等，栈顶符号出栈 + ，数值出栈 16 23
1. 23 + 16 = 39运算结果入栈，栈顶没有符号了符号+直接入栈
1. 数值1入栈，所有符号入栈完毕，出栈符号 + 出栈数值 1 39
1. 39 + 1 = 40 40
@author: muzili(李敷斌)
@date: 2021/7/20
@version: v0.0.1
@description: 数学表达式计算 */ public class MathElCalcu {

/**
- 声明数值栈 */ Stack numStack = new ArrayStack();
  
  /**
- 声明符号栈 */ Stack operatorStack = new ArrayStack();
  
  /**
- 运算结果 */ BigDecimal result = BigDecimal.ZERO;
  
  /**
- 运算符 */ Character operator;

Character[] operatorArr = {'+','-','*','/','(',')'};
/**
 * 计算
 * @param str
 * @return 计算结果
 */
public BigDecimal calc(String str){
    if (str == null || str.equals("")){
        throw new IllegalArgumentException("算术表达式不能为空！");
    }
    //判断括号是否匹配
    BracketMatch bracketMatch = new BracketMatch();
    if (!bracketMatch.isOk(str)) {
        throw new IllegalArgumentException("算术表达式错误！"+str);
    }
    //TODO 更多输入校验
    char[] chars = str.toCharArray();
    for (Character c : chars) {
        if (!Arrays.asList(operatorArr).contains(c)){
            numStack.push(BigDecimal.valueOf(Double.parseDouble(String.valueOf(c))));
            continue;
        }
        pushOperator(c);
    }
    BigDecimal num2 = numStack.pop();
    BigDecimal num1 = numStack.pop();
    operator = operatorStack.pop();
    BigDecimal result = calc(num1, num2, operator);
    return result;
}
/**
 * 运算符入栈
 * @param c
 */
private void pushOperator(Character c) {
    operator = operatorStack.pop();
    //如果栈顶没有元素 或 栈顶元素优先级低于当前符号直接入栈
    Character judgeSize = judgeSize(operator, c);
    if (operator == null || judgeSize.equals('<')){
        operatorStack.push(operator);
        operatorStack.push(c);
        return;
    }
    if (judgeSize.equals('=') && operator.equals('(') && c.equals(')')){
        return;
    }
    BigDecimal num2 = numStack.pop();
    BigDecimal num1 = numStack.pop();
    BigDecimal result = calc(num1, num2, operator);
    numStack.push(result);
    pushOperator(c);
}
/**
 * 计算
 * @param num1
 * @param num2
 * @param operator
 * @return 计算结果
 */
public BigDecimal calc(BigDecimal num1,BigDecimal num2,Character operator){
    switch (operator){
        case '+':
            result = num1.add(num2);
            System.out.println(num1+"+"+num2+"="+result);
            break;
        case '-':
            result = num1.subtract(num2);
            System.out.println(num1+"-"+num2+"="+result);
            break;
        case '*':
            result = num1.multiply(num2);
            System.out.println(num1+"*"+num2+"="+result);
            break;
        case '/':
            result = num1.divide(num2);
            System.out.println(num1+"/"+num2+"="+result);
            break;
    }
    return result;
}
/**
 * 判断大小
 * @param operator 栈顶符号
 * @param currOperator 当前符号 待入栈符号
 * @return 结果
 */
public Character judgeSize(Character operator,Character currOperator){
    if(operator == null){
        return '<';
    }
    switch (operator){
        case '+':
        case '-':
            switch (currOperator){
                case '*':
                case '/':
                case '(':
                    return '<';
                case '+':
                case '-':
                case ')':
                    return '>';
            }
        case '*':
        case '/':
            switch (currOperator){
                case '(':
                    return '<';
                case '+':
                case '-':
                case '*':
                case '/':
                case ')':
                    return '>';
            }
        case '(':
            switch (currOperator){
                case '+':
                case '-':
                case '*':
                case '/':
                    return '<';
                case '(':
                case ')':
                    return '=';
            }
        case ')':
            switch (currOperator){
                case '+':
                case '-':
                case '*':
                case '/':
                case ')':
                    return '>';
            }
    }
    return '<';
}
public static void main(String[] args) {
    MathElCalcu mathElCalcu = new MathElCalcu();
    System.out.println(mathElCalcu.calc("2+3*5+6+(1+5*3)+1"));
}

}

运行结果》》》 “D:\Program Files\Java\jdk1.8.0_191\bin\java.exe” “-javaagent:E:\Program Files\JetBrains\IntelliJ IDEA 2019.1.1\lib\idea_rt.jar=53003:E:\Program Files\JetBrains\IntelliJ IDEA 2019.1.1\bin” -Dfile.encoding=UTF-8 -classpath “D:\Program Files\Java\jdk1.8.0_191\jre\lib\charsets.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\deploy.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\access-bridge-64.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\cldrdata.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\dnsns.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\jaccess.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\jfxrt.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\localedata.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\nashorn.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\sunec.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\sunjce_provider.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\sunmscapi.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\sunpkcs11.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\zipfs.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\javaws.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\jce.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\jfr.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\jfxswt.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\jsse.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\management-agent.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\plugin.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\resources.jar;D:\Program Files\Java\jdk1.8.0_191\jre\lib\rt.jar;D:\workspace\learning\data-structure\target\classes” com.muzili.stack.MathElCalcu 3.05.0=15.00 2.0+15.00=17.00 17.00+6.0=23.00 5.03.0=15.00 1.0+15.00=16.00 23.00+16.00=39.00 39.00+1.0=40.00 40.00


- IDE符号匹配
```java
package com.muzili.stack;
import java.util.Scanner;
/**
 *
 * @author: muzili(李敷斌)
 * @date: 2021/7/20
 * @version: v0.0.1
 * @description: 通过栈实现括号匹配
 */
public class BracketMatch {
    Stack<Character> leftBracketStack = new ArrayStack<Character>();
    /**
     * 判断是否完全匹配
     * @param str
     * @return 是否完全匹配
     */
    public boolean isOk(String str){
        if (str == null || str.equals("")){
            return false;
        }
        char[] charArray = str.toCharArray();
        for (char c : charArray) {
            Character character;
            switch (c){
                case '{':
                case '[':
                case '(':
                    leftBracketStack.push(c);
                    break;
                case '}':
                    character = leftBracketStack.pop();
                    if (character == null || !character.equals('{')){
                        return false;
                    }
                    break;
                case ']':
                    character = leftBracketStack.pop();
                    if (character == null || !character.equals('[')){
                        return false;
                    }
                    break;
                case ')':
                    character = leftBracketStack.pop();
                    if (character == null || !character.equals('(')){
                        return false;
                    }
                    break;
                default:
                    break;
            }
        }
        return leftBracketStack.isEmpty();
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            BracketMatch bracketMatch = new BracketMatch();
            System.out.println("输入的内容是否匹配："+bracketMatch.isOk(scanner.nextLine()));
        }
    }
}

浏览器前进后退功能

基础数据结构-栈

1. 什么是栈？

1.1 栈的基本概念

1.2 栈的特点

2. 栈的实现

2.1 基于数组实现栈

2.3 数组实现VS链表实现

3. 栈的使用场景