数据结构与算法-栈

什么是栈
栈又称为堆栈，是一种运算受限定表。说是限定表是由于对于元素的入栈和出栈都在表末尾进行，换言之就是先进后出，其本质就是对表尾部元素进行操作。在计算机系统中，栈是具有以上属性的动态内存区域。由于数据结构都是数组和指针的组合，故我们可以用JAVA数组来进行模拟。

算法原理
定义变量：TOP-栈顶指针 N-当前数组容器长度 S-数组 X-元素
1、入栈(PUSH)算法
1.1 首先判断指针 TOP +1 > N-1，满足则进行动态扩容后进入下一步，否则直接进入下一步
1.2 TOP++ 增加指针指向栈顶
1.3 S(TOP) = X 将元素赋值给栈顶索引

2、出栈(POP)算法
2.1 首先判断 TOP-1 < 0，满足抛出异常没有可出栈元素，否则进入下一步
2.2 X=S(TOP) 获取待出栈元素已备后续返回使用
2.3 S(TOP) = NULL,TOP-- 置空栈顶元素，减少指针指向栈顶

小试牛刀
1、创建栈方法，并提供模拟动态扩容、出入栈、获取栈顶元素等方法

/**
 * 数据结构-栈
 * @author senfel
 * @version 1.0
 * @date 2022/11/24 11:01
 */
@Slf4j
public class Stack {
    /**
     * 栈数组
     */
    private Object[] elementArray;
    /**
     * 栈顶指针
     */
    private Integer top;
    /**
     * 栈深度
     */
    private Integer deepness;

    /**
     * 默认栈深度为10的构造方法
     */
    public Stack() {
        this.elementArray = new Object[10];
        this.top = -1;
        this.deepness = 10;
    }

    /**
     * 提供有个传入栈深度的构造方法
     * @param deepness
     */
    public Stack(Integer deepness) {
        this.elementArray = new Object[deepness];
        this.top = -1;
        this.deepness = deepness;
    }


    /**
     * 扩容方法
     * 1、判断是否需要扩容
     * 2、需要扩容则扩大两倍的量
     * @param topIndex
     * @author senfel
     * @date 2022/11/24 11:08
     * @return void
     */
    public void grow(Integer topIndex){
        //缓存当前栈深度
        Integer currentDeepness = deepness;
        //由于top为索引故栈顶深度 == index+ 1
        if(topIndex + 1 > deepness){
            //需要扩容并验证扩容后是否超过int取值范围
            if(currentDeepness * 2 > Integer.MAX_VALUE){
                deepness = Integer.MAX_VALUE;
            }else{
                deepness = currentDeepness * 2;
            }
            //对栈内元素重新分配索引
            elementArray = Arrays.copyOf(elementArray, deepness);
        }
    }


    /**
     * 验证栈是否为空
     * @author senfel
     * @date 2022/11/24 11:23
     * @return java.lang.Boolean
     */
    public Boolean isEmpty(){
        if(top > -1){
            return false;
        }else{
            return true;
        }
    }

    /**
     * 入栈
     * @param element
     * @author senfel
     * @date 2022/11/24 11:19
     * @return void
     */
    public void push(Object element){
        //扩容并移动栈顶指针
        grow(++top);
        //元素压入栈顶
        elementArray[top] = element;
    }

    /**
     * 获取栈顶元素
     * @author senfel
     * @date 2022/11/24 11:21
     * @return void
     */
    public Object peek(){
        if(isEmpty()){
            return null;
        }
        return elementArray[top];
    }

    /**
     * 弹出栈顶元素
     * @author senfel
     * @date 2022/11/24 11:24
     * @return java.lang.Object
     */
    public void pop(){
       //获取栈顶元素
        Object peek = peek();
        if(Objects.isNull(peek)){
            throw new EmptyStackException();
        }
        elementArray[top] = null;
        top--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

2、提供测试方法

   public static void main(String[] args) {
        Stack stack = new Stack(8);
        log.error("初始栈{}",Arrays.toString(stack.elementArray));
        //当前栈是否为空
        log.error("当前栈是否为空：{}",stack.isEmpty());
        for(int i = 0;i< 10;i++){
            stack.push(i);
        }
        log.error("入栈后的栈结构为{}",Arrays.toString(stack.elementArray));
        log.error("当前栈顶元素为：{}",stack.peek());
        //模拟出栈两次
        stack.pop();
        stack.pop();
        log.error("出栈两次栈后的栈结构为{}",Arrays.toString(stack.elementArray));
        log.error("当前栈顶元素为：{}",stack.peek());
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3、展示测试结果

11:46:30.740 - 初始栈[null, null, null, null, null, null, null, null]
11:46:30.743 - 当前栈是否为空：true
11:46:30.743 - 入栈后的栈结构为[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null, null, null, null, null, null]
11:46:30.743 - 当前栈顶元素为：9
11:46:30.743 - 出栈两次栈后的栈结构为[0, 1, 2, 3, 4, 5, 6, 7, null, null, null, null, null, null, null, null]
11:46:30.743 - 当前栈顶元素为：7