数据结构（2）：栈的原理和实现

2022-05-15 00:05:07

一、介绍

栈是一种数据先入后出，后入先出的数据结构。

如果图所示，将数字 10、15、6、9 存入栈后，从栈中取到的数据按顺序将会是 9、6、15、10。栈的结构像我们生活中的箱子，最先放入的物品将会在箱子的最底部，最后放入的数据在最上面，拿物品时也需要从最上面拿起。

二、代码实现

1、创建 MyStack 类作为自定义的栈

public class MyStack {

}

2、声明所需的属性

底层使用数组存储数据，也可以使用java的泛型替代Object类型。

private Object[] arr;//存储数据
private int top;//栈顶的位置

栈顶：整个栈最上面(最后入栈)的元素，也就是数组中最后存入的元素。

栈底：整个栈最下面(最先入栈)的元素，也就是数组中最先存入的元素。

3、栈的构造方法

public MyStack(){
    arr = new Object[10];
    top = -1;
}

/**
 * 参数为数组的初始长度
 * @param maxSize
 */
public MyStack(int maxSize){
    arr = new Object[maxSize];
    top = -1;
}

4、向栈中压入数据

底层的操作就是向数组中存入数据，由于top变量记栈顶的位置，所以top的值增加1后即为最新的栈顶的置。

 public void push(Object value) {
    arr[++top] = value;
}

5、弹出栈顶的数据

取得栈顶的数据，并将此数据将栈中移除。向栈中压入数据需要将记录栈顶的位置的变量top加1，同理，移除栈顶数据需要将top减1。

public Object pop(){
    return arr[top--];
}

6、查看栈顶数据

public Object peek(){
    return arr[top];
}

7、判断是否为空

public boolean isEmpty(){
    return top == -1;
}

8、判断是否存满

top的值等于数组最后一个元素的位置即为存满

public boolean isFull(){
    return top == arr.length-1;
}

9、完整代码

public class MyStack {
    private Object[] arr;//存储数据
    private int top;//栈顶的位置

    public MyStack() {
        arr = new Object[10];
        top = -1;
    }

    /**
     * 参数为数组的初始长度
     *
     * @param maxSize
     */
    public MyStack(int maxSize) {
        arr = new Object[maxSize];
        top = -1;
    }

    public void push(Object value) {
        arr[++top] = value;
    }

    /**
     * 弹出栈顶的数据
     * @return
     */
    public Object pop(){
        return arr[top--];
    }

    public Object peek(){
        return arr[top];
    }

    public boolean isEmpty(){
        return top == -1;
    }

    public boolean isFull(){
        return top == arr.length-1;
    }
}

三、验证

public static void main(String[] args) {
    MyStack stack = new MyStack(4);
    stack.push("a");
    stack.push("b");
    stack.push("c");
    stack.push("d");

    System.out.println("是否为空：" + stack.isEmpty());
    System.out.println("是否存满：" + stack.isFull());

    System.out.println("栈顶："+stack.peek());
    System.out.println("栈顶："+stack.peek());

    //弹出栈中所有数据
    while (!stack.isEmpty()){
        System.out.println(stack.pop());
    }

    System.out.println("是否为空：" + stack.isEmpty());
    System.out.println("是否存满：" + stack.isFull());
}

码农公寓