快捷導航

Java ArrayDeque實現(xiàn)Stack的功能

更新時間：2016年03月29日 11:53:49 作者：forrest420

這篇文章主要介紹了Java ArrayDeque實現(xiàn)Stack功能的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下

在J2SE6引入了ArrayDeque類，它繼承了Deque(雙向隊列)接口，使用此類可以自己實現(xiàn)java.util.Stack類的功能，去掉了java.util.Stack的多線程同步的功能。

例如創(chuàng)建一個存放Integer類型的Stack，只要在類中創(chuàng)建一個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數(shù)組最后的位置開始存儲的*/ 
 public void addFirst(E e) { 
    if (e == null) 
      throw new NullPointerException(); 
    elements[head = (head - 1) & (elements.length - 1)] = e;//首次數(shù)組容量默認為16，head=（0-1）&(16-1)=15 
    if (head == tail) 
      doubleCapacity(); 
  } 
 
/*每次擴容都按插入的先后順序重新放入一個新的數(shù)組中，最新插入的放在數(shù)組的第一個位置。*/ 
  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;   // 重新設(shè)置數(shù)組中的這個位置為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 
  }

以上就是本文的全部內(nèi)容，希望對大家學習java程序設(shè)計有所幫助。

您可能感興趣的文章: