Java中栈队列双端队列方法总结

2021.03.01 06:03 450
阅读约 5 分钟

Stack

java中的后入先出的栈结构,继承自Vector因此是一个线程安全的容器

类方法

stack的方法非常简单,只有下面五种方法

  • push:调用 Vector的addElement方法,将新元素 obj 插入到 Vector 维护的 elementData[] 数组中
    • elementData[elementCount++] = obj;
  • pop:调用 Vector的 removeElementAt(len - 1),将 Vector最后的一个弹出
  • peek:调用 Vector 的 elementAt(len - 1),返回 Vector 最后一个元素
  • empty:return size() == 0
  • search:返回该元素在栈中的索引
    • 调用 Vector的 lastIndexOf(o) 查询元素在数组的索引位置,返回 size() - 索引位置

LinkedList

LinkedList是典型的双端队列的实现类, 实现了Deque双端队列的接口,而Deque继承自Queue接口拥有先入先出的功能。

Queue接口

Queue添加元素的实现

  • add  调用 LinkedList中的 linkLast 方法将指定元素的添加到链表的尾部
  • offer 调用 add 方法

Queue删除元素的实现

  • poll 调用 unlinkFirst(f) 将链表的首节点移除
  • remove 调用removeFirst 再调用unlinkFirst(f) 将链表的首节点移除

Queue获取队列顶部元素的实现

  • peek  返回final Node<E> f = first;

Deque接口

Deque接口要稍微复杂一些,为了便于理解,我们稍微整理一下方法,淦,这么多看的眼花缭乱,但是细品可以看出一些规律

双端队列既拥有栈的后入先出的特性,又有队列先入先出的特性,因此我们可以将这些方法稍微分类一下,其实很多方法是一样。

  • push  ==  linkFirst
    • offerFirst  == addFirst  
    • addFirst  ==  linkFirst
  • add == linkLast
    • offer == linkLast
    • addLast == linkLast
    • offerLast == addLast
  • pop == removeFirst 
    • remove == removeFirst
    • removeFirst == unlinkFirst  空时抛 NoSuchElementException 异常
    • poll == unlinkFirst     空时返回null
    • pollFirst == unlinkFirst  空时返回null
  • peek  返回final Node<E> f = first;
    • peekFirst  返回 first
    • getFirst 返回 first 空时抛 NoSuchElementException 异常
  • peekLast 返回 final Node<E> l = last;
    • getLast 返回 last 空时抛 NoSuchElementException 异常
  • pollLast == unlinkLast  空时返回null
    • removeLast == unlinkLast   空时抛 NoSuchElementException 异常

 

字数:1356 发布于 7 个月前
Copyright 2018-2021 Siques