Java ArrayDeque实现Stack的功能

在J2SE6引入了ArrayDeque类，它继承了Deque(双向队列)接口，使用此类可以自己实现java.util.Stack类的功能，去掉了java.util.Stack的多线程同步的功能。

例如创建一个存放Integer类型的Stack，只要在类中创建一个ArrayDeque类的变量作为属性，之后定义的出栈、入栈，观察栈顶元素的操作就直接操作ArrayDeque的实例变量即可。 

import java.util.ArrayDeque;
import java.util.Deque;

public class IntegerStack {
  private Deque<Integer> data = new ArrayDeque<Integer>();

  public void push(Integer element) {
    data.addFirst(element);
  }

  public Integer pop() {
    return data.removeFirst();
  }

  public Integer peek() {
    return data.peekFirst();
  }

  public String toString() {
    return data.toString();
  }

  public static void main(String[] args) {
    IntegerStack stack = new IntegerStack();
    for (int i = 0; i < 5; i++) {
      stack.push(i);
    }
    System.out.println(stack);
    System.out.println("After pushing 5 elements: " + stack);
    int m = stack.pop();
    System.out.println("Popped element = " + m);
    System.out.println("After popping 1 element : " + stack);
    int n = stack.peek();
    System.out.println("Peeked element = " + n);
    System.out.println("After peeking 1 element : " + stack);
  }
}

java.util.ArrayDeque的源码：    

private transient E[] elements;
 private transient int head;
 private transient int tail;

/*此处存放e的位置是从elements数组最后的位置开始存储的*/
 public void addFirst(E e) {
    if (e == null)
      throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;//首次数组容量默认为16，head=（0-1）&(16-1)=15
    if (head == tail)
      doubleCapacity();
  }

/*每次扩容都按插入的先后顺序重新放入一个新的数组中，最新插入的放在数组的第一个位置。*/
  private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
      throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = (E[])a;
    head = 0;
    tail = n;
  }

  public E removeFirst() {
    E x = pollFirst();
    if (x == null)
      throw new NoSuchElementException();
    return x;
  }

  public E pollFirst() {
    int h = head;
    E result = elements[h]; // Element is null if deque empty
    if (result == null)
      return null;
    elements[h] = null;   // 重新设置数组中的这个位置为null，方便垃圾回收。
    head = (h + 1) & (elements.length - 1);//将head的值回退，相当于将栈的指针又向下移动一格。例如，12--〉13
    return result;
  }

  public E peekFirst() {
    return elements[head]; // elements[head] is null if deque empty
  }

以上就是本文的全部内容，希望对大家学习java程序设计有所帮助。