数据结构 | 栈 Stack

38 次访问 2020-04-09

yzt

栈 Stack

栈是一种特殊的线性表, 只能在一端（栈顶）进行操作
向栈中添加元素的操作，即 push，入栈，压栈
从栈中移除元素的操作(只能移除栈顶的元素)，即 pop，出栈，弹栈
栈遵循后进先出原则：Last In First Out，LIFO

实现栈

栈的内部实现可以使用动态数组或双向链表，因为栈的主要操作是在尾部添加或删除元素，所以入栈出栈复杂度都是 $ O(1) $（注意必须是双向链表，才能保证 $ O(1) $ 的复杂度）
虽然可以继承 ArrayList 或 LinkedList 来实现栈，但是 ArrayList 或 LinkedList 中栈不需要的方法也会继承过来，比如向栈中某位置插入或删除
可以使用组合的方式实现栈，即在栈的类内部声明一个私有的 ArrayList 或 LinkedList 对象供自己使用
JDK 源码的原生 Stack 数据结构继承于 Vector（Vector 可以看做是线程安全的 ArrayList）

import java.util.ArrayList;
import java.util.List;

public class Stack<E> {

    // 声明一个 List 用于存储数据
    private List<E> list;

    public Stack() {
        // 也可以用我们自己写的 ArrayList 或者 LinkedList（双向链表） 实现
        list = new ArrayList<>();
    }

    public int size() {
        return list.size();
    }

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

    public void clear() {
        list.clear();
    }

    // 将一个元素压入栈中
    public void push(E ele) {
        list.add(ele);
    }

    // 返回并弹出栈顶元素
    public E pop() {
        return list.remove(list.size()-1);
    }

    // 查看栈顶元素，但不弹出
    public E top() {
        return list.get(list.size()-1);
    }
}

栈 Stack

实现栈

参考