数据结构-栈(Stack)

栈（stack）又名堆栈是一种特殊的线性表，只能在一端进行操作

• 往栈中添加元素的操作，一般叫做 push，入栈
• 从栈中移除元素的操作，一般叫做 pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）
• 后进先出的原则，Last In First Out，LIFO

这里说的“栈”与内存中的“栈空间”是两个不同的概念

栈的接口设计

◼int size(); // 元素的数量
◼ boolean isEmpty();// 是否为空
◼ void push(E element)；// 入栈
◼ E pop(); // 出栈
◼E top(); // 获取栈顶元素
◼ void clear();// 清空

栈的内部实现其实可以直接利用前面章节提到的数据结构(动态数组、链表)

package com.njf;

public class Stack<E> {
    private ArrayList<E> list = new ArrayList<>();
    public void clear() {
        list.clear();
    }
    
    public int size() {
        return list.size();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public void push(E element) {
        list.add(element);
    }

    public E pop() {
        return list.remove(list.size() - 1);
    }

    public E top() {
        return list.get(list.size() - 1);
    }
}

调用验证

package com.njf;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(11);
        stack.push(22);
        stack.push(33);
        stack.push(44);
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

可以看到出栈的顺序如下

44
33
22
11