数据结构与算法（第一季）：栈

一、栈

• 栈是一种特殊的线性表, 只能在一段进行操作
• 往栈中添加元素的操作, 一半叫做push, 入栈
• 从栈中移除元素的操作, 一般叫做pop, 出栈(只能移除栈顶的元素)
• 栈遵守后进先出的原则, Last In First Out, LIFO

image

<figcaption></figcaption>

二、栈的接口设计

int size();
boolean isEmpty();
void push(E element);
E pop();
E top();
void clear();
复制代码

栈的内部实现可以使用动态数组或链表

三、栈的实现

• 可以使用动态数组实现栈

public class Stack<E> {
    // 使用 动态数组存储数组
    private ArrayList<E> list;
    public Stack() {
        // 初始化方法中创建列表
        this.list = new ArrayList<>();
    }
    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);
    }
    public void clear() {
        // 清空栈, 就是清空列表
        list.clear();
    }
}