博客

Stack

• Stack栈采用的是一种先进先出的操作。

• Stack类继承自Vector类（向量）。关于Vector的内容：https://www.runoob.com/java/java-vector-class.html

• 这个类中存在五个方法，他们的作用分别是：

  • 入栈操作
  • 出栈操作
  • 查看栈顶元素
  • 返回该栈是否为空
  • 查看指定元素距离栈顶的长度

• 
  入栈操作
  

  public E push(E item) {
          addElement(item);
  
          return item;
  }
  
  //addElement（）
  public synchronized void addElement(E obj) {
          modCount++;//记录结构性改变的次数：改变list的长度
    		//elementCount是数组的个数
    //判断当前数组是否需要扩容
          ensureCapacityHelper(elementCount + 1);
    		//将obj加入到数组中
          elementData[elementCount++] = obj;
  }
  

• 
  出栈操作
  

  public synchronized E pop() {
          E       obj;
          int     len = size();//数组的长度
  
          obj = peek();//返回栈顶元素值
          removeElementAt(len - 1);
  
          return obj;
  }
  
  //removeElementAt（）
  public synchronized void removeElementAt(int index) {//index指的元素在数组中的下标
          modCount++;//结构性改变的次数+1
          if (index >= elementCount) {//下标值>=数组长度，抛出异常
              throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                       elementCount);
          }
          else if (index < 0) {
              throw new ArrayIndexOutOfBoundsException(index);
          }
    		//该元素后面的元素个数
          int j = elementCount - index - 1;
          if (j > 0) {
            //原数组，原数组起始位置，目标数组，目标数组起始位置，复制的长度
              System.arraycopy(elementData, index + 1, elementData, index, j);
          }
          elementCount--;//数组元素个数-1
          elementData[elementCount] = null;/* 设置数组最后一个元素值为空，因为元素组那个位置是有值的to let gc do its work */
  }
  

• 
  查看栈顶元素，但是不出栈
  

  public synchronized E peek() {
          int     len = size();//数组的长度
  
          if (len == 0)
              throw new EmptyStackException();
          return elementAt(len - 1);
  }
  
  //elementAt（）
  public synchronized E elementAt(int index) {
    		//判断下表是否大于等于数组长度
          if (index >= elementCount) {
              throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
          }
  
          return elementData(index);
  }
  
  //elementData（）
  E elementData(int index) {
    		//返回指定下标中数组的值
          return (E) elementData[index];
  }
  

• 
  查看该栈是否为空
  

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

• 
  查看指定元素在栈中是否存在，存在的话返回距离栈顶的长度
  

  public synchronized int search(Object o) {
          int i = lastIndexOf(o);
  
          if (i >= 0) {
            //i是元素在数组中的下标值，栈顶元素在数组的最后一个，如果返回该元素距离栈顶的距离，需要做运算
              return size() - i;
          }
          return -1;
  }
  
  //lastIndexOf()
  public synchronized int lastIndexOf(Object o) {
          return lastIndexOf(o, elementCount-1);
  }
  
  //lastIndexOf()
  public synchronized int lastIndexOf(Object o, int index) {
          if (index >= elementCount)
              throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
  
    		//在数组中，倒序查找，最后返回元素下标值
          if (o == null) {
              for (int i = index; i >= 0; i--)
                  if (elementData[i]==null)
                      return i;
          } else {
              for (int i = index; i >= 0; i--)
                  if (o.equals(elementData[i]))
                      return i;
          }
          return -1;
  }