Java 基础 - 06 List 之 Stack 以及List的相关总结

发布时间:2024年01月16日

Java的栈,算是我们在Java中常见的一种数据结构,他遵循先进后出的原则(Last-In-First-Out,LIFO)的原则,在Java中,Stack是通过继承自Vector类实现的。

在这里插入图片描述
如上图所示,我们的stack继承自Vector。

我们来看一个简单的案例,实现一个简单的先进后出demo:

 public static void main(String[] args) {
        // 创建一个Stack对象
        Stack<String> stack = new Stack<>();

        // 入栈操作
        stack.push("Java");
        stack.push("Python");
        stack.push("C++");

        // 出栈操作
        while (!stack.isEmpty()) {
            String element = stack.pop();
            System.out.println("出栈元素: " + element);
        }
    }

在这里插入图片描述
由于Stack继承自Vector,故而Stack中并没有许多新的方法,一般主要操作栈就是在Stack中进栈和出栈,当然还可以判断栈是否为空,以及在栈中搜索相关元素。这个栈里边很多方法来自Vector,直接使用就行,值得注意的是,在Stack中,Java通过五个操作对Vector进行相关拓展,他允许将向量视为堆栈。Stack是Vector的增强类,堆栈顶部对应向量末尾。

在这里插入图片描述

boolean empty():测试堆栈是否为空。

public boolean empty() {
	return size() == 0;
}

peek() :查看堆栈顶部的对象,但不从堆栈中移除它。

public synchronized E peek() {
	//获取向量容量大小
	int	len = size();
	if (len == 0)
	    throw new EmptyStackException();
	return elementAt(len - 1);//调用父类Vector的elementAt方法
}

注意堆栈顶部的对象的对象索引对应的是向量末尾。

E pop(): 移除堆栈顶部的对象,并作为此函数的值返回该对象。

public synchronized E pop() {
	E	obj;
	//获取向量大小
	int	len = size();
	//获取堆栈顶部的对象
	obj = peek();
	//调用父类Vector的removeElementAt方法,移除末尾元素
	removeElementAt(len - 1);
	return obj;
}

E push(E item):把项压入堆栈顶部。

public E push(E item) {
	//调用父类Vector的addElement方法,添加元素至向量末尾
	addElement(item);
	return item;
}

int search(Object o):返回对象在堆栈中的位置,以 1 为基数。

public synchronized int search(Object o) {
	//调用父类Vector的lastIndexOf方法
	//返回此向量中最后一次出现的指定元素的索引,从末尾向前搜索,如果未找到该元素,则返回 -1。
	int i = lastIndexOf(o);
	if (i >= 0) {
	    return size() - i;
	}
	return -1;
}

List集合总结

ArrayList

  • 默认初始值容量为10,数组大小可变;
  • 是一个有序的,可以重复的, 允许为NULL值的
  • 是一个非同步的,快速失败机制
  • 底层是以transient Object[] 形式存储的,适用于快速随机访问元素。
  • 每次扩容在原有的基础上扩充 = 原有容量 * 1.5 + 1
  • 扩容增量 > 实际添加的元素数,保证不需要每次添加元素的时候都进行库容,从而提高性能。
  • iterator()调用的是父类的AbstractList方法
  • 数组大小理论上是由Max值构成,index的类型为int。

fail-fast(快速失败机制)就是在做系统设计的时候先考虑异常情况,一旦发生异常,直接停止并上报。

LinkedList

  • 是List接口的链表实现,支持序列化、有序、值可以为NULL。
  • 双向链表运行将链接列表作用于堆栈、队列或者双端队列。
  • 适用于随机快速插入和删除。
  • 也是非同步的,快速失败机制
  • 在条件满足的情况下,其内存可以无限大,链式存储
  • iterator()由其内部类ListItr实现。

CopyOnWriteArrayList

  • 用于读多写少的情况下的并发场景
  • 复制用法会存在导致内存占用过高的问题。
  • 保证数据的最终一致性,但无法保证数据的实时性
  • 其内部使用的锁是可重入的互斥锁ReentrantLock来保证数据同步。
  • 其使用了Volatile关键字修饰数组,从而保证了可见性、
  • 其是读写分离的。
  • 在调用相关方法的时候,addIfAbsent可以做到不添加重复的元素。
  • 在使用的过程中需要注意的点,采用CopyOnWriteArrayList,也是就COW设计,在扩容的时候,需要按需扩容,避免内存浪费。
  • iterator()由其内部类COWIterator实现。

Vector

  • 可以实现增长的对象数组,其默认初始容量为10;
  • 可以使用整数索引进行访问,根据我们的实际需要可以进行增大和缩小。
  • 通过synchronized修饰每个方法,保证同步性,快速失败机制。
  • iterator()调用的是父类AbstractList方法。
  • 扩容方案 =》 容量增量>0,则预期为:现有容量+容量增量,否则为:现有容量*2),计算后与要求的最小容量比较,取最大值。 保证不必每次add时都进行扩容,提高性能。

Stack

  • Stack是先进后出(LIFO)的对象堆栈,实际上继承自Vector。
  • 他是Vector的增强类,堆栈顶部都对应向量尾部。
  • 在首次创建栈的时候,不包含项。
  • 特点是只能在栈顶进行插入和删除操作,即先进后出。
  • 不建议直接使用Stack类:在Java中,Stack类是通过继承自Vector类来实现的,而Vector类是一个线程安全的动态数组。由于Stack类继承了Vector类的所有方法,包括一些不安全的方法,因此在实际使用中,建议使用更为常见的LinkedList类来实现栈,或者使用Deque接口的实现类,如ArrayDeque。
  • 在使用栈时,需要注意空栈检查,避免栈溢出,不支持随机访问,以及选择合适的实现方式等。
  • 栈有一个固定的容量,当栈中的元素数量超过容量时,会导致栈溢出(StackOverflowError)。因此,在使用栈时,应该注意控制入栈的数量,避免溢出。
  • 不支持随机访问:栈是一种顺序访问的数据结构,只能从栈顶进行入栈和出栈操作。它不支持随机访问,即不能直接访问栈中的任意位置的元素。
  • 适用场景:栈适用于需要先进后出的场景,比如函数调用、表达式求值、括号匹配等。在这些场景下,栈可以提供便捷的操作和管理。

由于ArrayList是数组存储形式,在随机查询方面会比较快。若每次add或remove时均在末尾,ArrayList会比较快,直接通过index操作。但若随机add或remove,LinkedList链式存储,相比ArrayList少了System.arrayCopy操作,会快一点,且ArrayList每次随机添加和删除都需要移动元素,故而也会影响相关性能。Vector每个方法都加上synchronized,保证了同步同时,牺牲了性能。

文章来源:https://blog.csdn.net/qq_45922256/article/details/135630538
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。