栈 Stack

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

栈 Stack

实现栈

  • 栈的内部实现可以使用动态数组双向链表,因为栈的主要操作是在尾部添加或删除元素,所以入栈出栈复杂度都是 $ O(1) $(注意必须是双向链表,才能保证 $ O(1) $ 的复杂度)
  • 虽然可以继承 ArrayList 或 LinkedList 来实现栈,但是 ArrayList 或 LinkedList 中栈不需要的方法也会继承过来,比如向栈中某位置插入或删除
  • 可以使用组合的方式实现栈,即在栈的类内部声明一个私有的 ArrayList 或 LinkedList 对象供自己使用
  • JDK 源码的原生 Stack 数据结构继承于 Vector(Vector 可以看做是线程安全的 ArrayList)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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);
    }
}

参考