stack源码分析

简介:
## 一、简介
![stack类图.png](http://upload-images.jianshu.io/upload_images/1541350-5fe08669097e7ac0.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

栈是数据结构中一种很重要的数据结构类型,因为栈的后进先出功能是实际的开发中有很多的应用场景。Java API中提供了栈(Stacck)的实现。Stack类继承了Vector类,而Vector类继承了AbstractList抽象类,实现了List类,Cloneable接口,RandomAcces接口以及Serializable接口。
## 二、源码阅读
#### 1.构造方法
```java
public Stack() {
}
```
创建一个空栈。
#### 2.入栈push
```java
public E push(E item) {
    addElement(item);
    return item;
}
```
```java
public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}
```
入栈是一个同步的方法,调用Vector的**addElement**方法,也是一个同步方法,先将修改次数加一,之后调用**ensureCapacityHelper**确认数组有足够的空间能够容纳新的元素。最后将元素新增到数组,即Vector的末尾。
#### 3.出栈pop
```java
public synchronized E pop() {
    E       obj;
    int     len = size();
    obj = peek();
    removeElementAt(len - 1);

    return obj;
}
```
出栈同样是一个同步方法,先定义一个泛型对象obj,获取到数组长度len,然后调用**peek()**方法,获取栈顶的元素赋值给obj,然后删除栈顶元素。
```java
public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}
```
很显然,peek()方法直接调用了Vector的elementAt方法,该方法不删除栈顶的元素。
#### 4.判断栈是否为空
```java
/**
 * 通过数组长度判断栈是否为空。
 *
 * @return  <code>true</code> if and only if this stack contains
 *          no items; <code>false</code> otherwise.
 */
public boolean empty() {
    return size() == 0;
}
```
#### 5.查询元素到栈顶的距离
```java
/**
 * Returns the 1-based position where an object is on this stack.
 * If the object <tt>o</tt> occurs as an item in this stack, this
 * method returns the distance from the top of the stack of the
 * occurrence nearest the top of the stack; the topmost item on the
 * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
 * method is used to compare <tt>o</tt> to the
 * items in this stack.
 *
 * @param   o   the desired object.
 * @return  the 1-based position from the top of the stack where
 *          the object is located; the return value <code>-1</code>
 *          indicates that the object is not on the stack.
 */
public synchronized int search(Object o) {
    int i = lastIndexOf(o);
    if (i >= 0) {
        return size() - i;
    }
    return -1;
}
```
一个同步方法,找到指定元素o到栈顶的距离,可以看到用到了lastIndexOf方法,如果找不到元素,则返回-1。
## 三、总计
通过源码我们可以看到Vector底层是一个数组,说明Stack的实现是通过数组来实现的,然后通过对数组的操作来模仿栈的各种功能。而且在源码中Vector的很多方法都是synchronized 的,也就是说是线程安全,所以说在多线程中是可以安全使用的,不过这样效率上肯定是会降低的。
目录
打赏
0
0
0
0
2
分享
相关文章
C++初阶--queue和stack
C++初阶--queue和stack
Java Review - Queue和Stack 源码解读
Java Review - Queue和Stack 源码解读
86 0
Collection-Stack&Queue源码解析
Collection-Stack&Queue源码解析
119 0
C++入门10——stack与queue的使用
C++入门10——stack与queue的使用
66 0
【STL】stack与queue的底层原理及其实现
【STL】stack与queue的底层原理及其实现
【C++杂货铺】探索stack和queue的底层实现
【C++杂货铺】探索stack和queue的底层实现
123 0
【C++初阶】十、STL---stack&&queue(总)
目录 一、stack介绍和使用 1.1 stack的介绍 1.2 stack的使用 二、queue的介绍和使用 2.1 queue的介绍 2.2 queue的使用 三、容器适配器 四、deque简单了解 五、stack模拟实现 六、queue模拟实现
137 0
【C++初阶】十、STL---stack&&queue(总)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等