Java Collection 05 - Stack

  关于 java.util.Stack<E> 的部分笔记,这是一种先进后出的数据结构,对外暴露的操作方法API数量有限。本文演示代码段的执行环境基于JDK版本1.7

概述

  Stack是一种以Vector为基础,具有先进后出(last-in-first-out或者LIFO)特性的数据结构。Stack只有为数不多的方法可以实现元素的存储和输出操作,其中push()方法用于将一个元素存储到Stack集合的顶部位置, pop()方法则从顶部取出一个元素并将次顶部的元素推到顶部位置, peek()仅仅是获取到顶部的元素, empty()方法用来判断当前Stack是否为空, search()方法则用来计算某个特定元素到Stack顶部的距离。

  如果需要用到LIFO特性的数据结构,Deque是一种比Stack更能满足要求的数据结构。Deque能够提供比Stack更为丰富的操作方法API,在实际使用时可以优先考虑Deque。

继承关系

1
2
3
4
5
6
// Stack<E>
--java.lang.Object
--java.util.AbstractCollection<E>
--java.util.AbstractList<E>
--java.util.Vector<E>
--java.util.Stack<E>

实现接口

类名 实现接口
Stack<E> Iterable<E>, Collection<E>, List<E>, RandomAccess, Serializable, Cloneable

Stack

Constructor Summary

public Stack()

1
2
public Stack() {
}

  初始化一个Stack集合。初始化之后,Stack是一个不含有任何元素的空集合。

部分方法

public E push(E item)

1
2
3
4
5
public E push(E item) {
addElement(item);

return item;
}

  将元素item压入到Stack栈顶部位置。实际调用的是Vector的addElement(E obj)方法。

public synchronized E pop()

1
2
3
4
5
6
7
8
9
public synchronized E pop() {
E obj;
int len = size();

obj = peek();
removeElementAt(len - 1);

return obj;
}

  返回并退出Stack栈顶部位置的元素。首先通过Vector的size()方法获取栈顶位置下标,然后peek()方法会返回处于栈顶位置的元素,最后通过Vector的removeElementAt(int index)方法删除len-1(也就是栈顶位置)的元素。

public synchronized E peek()

1
2
3
4
5
6
7
public synchronized E peek() {
int len = size();

if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}

  返回Stack栈顶部位置的元素。该方法仅返回顶部位置的元素,不会执行删除操作。通过Vector的size()方法得到栈顶位置下标,然后通过Vector的elementAt(int index)直接返回栈顶元素。

public boolean empty()

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

  判断当前栈是否为空。

public synchronized int search(Object o)

1
2
3
4
5
6
7
8
public synchronized int search(Object o) {
int i = lastIndexOf(o);

if (i >= 0) {
return size() - i;
}
return -1;
}

  返回元素o在栈中的位置。实际返回的当前元素o与栈顶位置之间的距离,且返回的是栈中距离栈顶位置最近的元素o的位置。如果元素o不存在与栈中,那么就返回-1。

涉及基础知识点

  1. NIL

参考文献

  1. NIL




------------- End of this article, thanks! -------------


  版权声明:本文由Nathan R. Lee创作和发表,采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可,转载请注明作者及出处。
  本文作者为 Nathan R. Lee
  本文标题为 Java Collection 05 - Stack
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-Stack.html