Java ArrayDeque实现Stack的功能

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 data = new ArrayDeque();

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("AfrlHIlNMater 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]; // elemerlHIlNMants[head] is null if deque empty

}

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。