【数据结构】——栈(Last In First Out)与队列(First In First Out)详解

栈的概念

栈(Last InFirst Out)是一种有着独特元素序列的数据结构，其主要特点就是后进先出，在外面生活中有很多像类型的特征，当浏览网页时，一般都有后退键，这个后退键就运用了栈思想，还有手枪子弹的结构。

栈只能在某一端的插入和删除，满足插入和删除的一端称为栈顶，另一端称为栈底，
栈的插入过程也叫进栈，也叫压栈，删除过程被称作为出栈

上述集合框架中，Stack时继承Vetor类的，Vector跟ArrayList一样，是一个动态的顺序表，但是Vetor时线程安全的

栈的顺序储存结构与模拟实现

栈的顺序储存结构其底层逻辑时数组，当压栈的过程就是在数组的数组的尾部添加一个元素，其出栈的过程就是将尾部最后一个元素给pop出来。

public class MyStack {
    //用数组实现栈
    private int[] array;
    public int size;

    public MyStack() {
        this.array = new int[3];
    }

    public int push(int e){
        ensureCapacity();
            array[size++] = e;
            return e;
    }

    public int pop(){
        if(empty()) return -1;
        int e = peek();
        size--;
        return e;
    }
    public int peek(){
        if(empty()) throw new RuntimeException("栈为空，无法peek");
        return array[size-1];
    }

    public int size(){
        return size;
    }

    public void ensureCapacity(){
        if(size == array.length){
            this.array = Arrays.copyOf(array,size*2);
        }
    }

    public boolean empty(){
        return size == 0;
    }
}
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