新手学源码__Stack底层实现

水深无声 2022-05-25 05:08 179阅读 0赞

## 前言 ##

继昨天学习的Vector，今天来看看栈Stack实现，之所以放在集合这个专栏里面是因为java stack实现的底层是vector

## Stack ##

栈的方法很简单

<table> 
 <thead> 
  <tr> 
   <th align="center">方法</th> 
   <th align="center">作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">empty</td> 
   <td align="center">判断一个栈是否为空</td> 
  </tr> 
  <tr> 
   <td align="center">peek</td> 
   <td align="center">返回栈顶元素</td> 
  </tr> 
  <tr> 
   <td align="center">pop</td> 
   <td align="center">出栈，并返回被弹出栈的对象</td> 
  </tr> 
  <tr> 
   <td align="center">push</td> 
   <td align="center">入栈，并返回入栈的对象</td> 
  </tr> 
  <tr> 
   <td align="center">search</td> 
   <td align="center">从栈顶开始向下寻找第一个匹配的对象</td> 
  </tr> 
 </tbody> 
</table>

## 具体实现 ##

构造方法

public Stack() {
        }

由于使用的是vector，所以构造方法里面啥也没有并不要实现啥东西

empty

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

只要看vector数组的大小是否==0

peek

public synchronized E peek() {
            int     len = size();
    
            if (len == 0)
                throw new EmptyStackException();
            return elementAt(len - 1);
        }

这里我们需要好好看一下，数组的尾部是作为的栈顶元素，为什么呢？主要是pop，接着往下看pop

pop

public synchronized E pop() {
            E       obj;
            int     len = size();
    
            obj = peek();
            removeElementAt(len - 1);
    
            return obj;
        }

调用了vector的removeElementAt方法，在我们之前的一片博文中，我们知道在remove指定的index的时候，会执行一次copy数组的操作，如果栈顶设置在尾部，这个数组复制的过程减少很大的开销，PS，如果你对数组的复制不知道，请参考上一篇集合vector的博文。

push

public E push(E item) {
            addElement(item);
    
            return item;
        }

push的操作也很简单

## 总结 ##

stack的操作是简单的，通过学习我知道了这两个细节

*  java的栈实现是vector
 *  java的栈顶是vector的数组尾