数据结构-03-栈

1-栈的结构和特点

先进后出，后进先出是栈的特点；

从图中，我们看到A入栈先放入底部，然后依次B和C；出栈的顺序依次是C-B-A；这种结构只能在一端操作。所以当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出（last–in–first–out(LIFO) ）、先进后出的特性，我们就应该首选“栈”这种数据结构。

2-栈的实现

我们可以使用数组和链表来实现栈，下面我们基于数组来现实一个基础功能的栈。

@Getter
@Setter
public class MyArrayStack {

    private Object[] elementData;//存储元素的数组
    private int elementCount;//元素的个数
    private int capacity;//容量

    public MyArrayStack(int capacity) {
        this.elementData = new Object[capacity];
        this.capacity = capacity;
        this.elementCount = 0;
    }

    // 入栈操作
    public boolean push(Objectitem) {
        if (elementCount == capacity) return false;
        elementData[elementCount] = item;
        ++elementCount;
        return true;
    }

    // 出栈操作
    public Object pop() {
        if (elementCount == 0) return null;
        Object tmp = elementData[elementCount-1];
        --elementCount;
        return tmp;
    }
}


@Slf4j
public class TestStack {
    public static void main(String[] args) {
        MyArrayStack stack=new MyArrayStack(3);
        log.info("push1={}",stack.push("hello"));
        log.info("push2={}",stack.push("java"));
        log.info("push3={}",stack.push("world"));
        log.info("push4={}",stack.push("china"));
        log.info("pop1={}",stack.pop());
        log.info("pop2={}",stack.pop());
        log.info("pop3={}",stack.pop());
        log.info("pop4={}",stack.pop());
    }
}

控制台输出：

10:19:38.417 [main] INFO c.y.d.statck.TestStack – push1=true
10:19:38.423 [main] INFO c.y.d.statck.TestStack – push2=true
10:19:38.423 [main] INFO c.y.d.statck.TestStack – push3=true
10:19:38.424 [m ain] INFO c.y.d.statck.TestStack – push4=false
10:19:38.424 [main] INFO c.y.d.statck.TestStack – pop1=world
10:19:38.424 [main] INFO c.y.d.statck.TestStack – pop2=java
10:19:38.424 [main] INFO c.y.d.statck.TestStack – pop3=hello
10:19:38.424 [main] INFO c.y.d.statck.TestStack – pop4=null