Java ArrayDeque实现Stack的功能

2020-04-14 11:27forrest420 JAVA教程

这篇文章主要介绍了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 

									  }