Stack(栈)实现了一个后进先出(LIFO)的数据结构。该类继承了Vector类,是通过调用父类Vector的方法实现基本操作的。
Stack共有以下五个操作:
put:将元素压入栈顶。
pop:弹出栈顶元素(返回栈顶元素,并删除)。
peek:取栈顶元素(不删除)。
empty:判断栈是否为空。
search:搜索一个元素是否在栈里,并返回其到栈顶的距离。
public class Stack<E> extends Vector<E> { public Stack() { } public E push(E item) { addElement(item); return item; } public synchronized E pop() { E obj; int len = size(); obj = peek(); removeElementAt(len - 1); return obj; } public synchronized E peek() { int len = size(); if (len == 0) throw new EmptyStackException(); return elementAt(len - 1); } public boolean empty() { return size() == 0; } public synchronized int search(Object o) { int i = lastIndexOf(o); if (i >= 0) { return size() - i; } return -1; } /** use serialVersionUID from JDK 1.0.2 for interoperability */ private static final long serialVersionUID = 1224463164541339165L; }
在之前源码阅读中我们知道vector是通过数组实现的。这里Stack又是通过Vector实现的,接下来我们挨个看其方法的实现。首先明确一点,stack是线程安全的。
(1)put
put方法并没有被synchronized修饰,因为该方法里面只有一条语句,调用Vector的addElement(item)方法,意思是在数组末尾插入一个元素,而addElement是被synchronized修饰的,所以put方法也是线程安全的。
(2)peek
首先获取数组的size,若为0,则报EmptyStackException异常。然后返回数组的最后一个元素。
(3)pop
先通过peek获取栈顶元素(数组最后一个元素),然后调用removeElementAt方法删除栈顶元素,最后返回之前获取的栈顶元素。
(4)search
通过lastIndexOf方法从后往前遍历找到匹配元素并获取所在位置的索引号i,然后通过size() - i返回其深度(到栈顶的距离)。若没有找到则返回-1。
总结
其实栈这种数据结构可以简单的通过一个数组进行模拟。
下面是我自己用1个数组实现的可扩容的栈MyStack
package com.ouym.test; import java.util.Arrays; import java.util.EmptyStackException; public class MyStack<E> { private Object[] elementData; private int elementCount; //表示当前栈存放的数据量 public MyStack() { this(10); } public MyStack(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity); elementData = new Object[initialCapacity]; } //扩容栈,扩容方式:新容量=旧容量*2 private void grow() { int capacity = elementData.length; capacity = capacity << 1; if (capacity < 0) { throw new OutOfMemoryError(); } elementData = Arrays.copyOf(elementData, capacity); } public E put(E item) { if (elementCount == elementData.length) { grow(); } elementData[elementCount++] = item; return item; } @SuppressWarnings("unchecked") public E peek() { if (empty()) { throw new EmptyStackException(); } return (E) elementData[elementCount - 1]; } public E pop() { E item = peek(); elementData[elementCount--] = null; return item; } public boolean empty() { return elementCount == 0; } public int size(){ return elementCount; } public int search(E item) { if (item == null) { for (int i = elementCount - 1; i >= 0; i--) if (elementData[i] == null) return i; } else { for (int i = elementCount - 1; i >= 0; i--) { if (item.equals(elementData[i])) { return elementCount - i; } } } return -1; } }
--------------------THE END--------------------