栈是重要的数据结构，从数据结构角度看，栈也是线性表，其特殊性在栈的基本操作是线性表的子集。Stack作为最基本的数据结构，在JDK代码中，也有它的实现，java.util.Stack类是继承了Vector类，来实现了栈的基本功能。
1.栈的基本原理
栈（Stack）是限定仅在表尾进行插入或者删除操作的线性表。因此，对于栈来说，表尾端有特殊含义，成为栈顶，表头称之为栈底。
由下图可以看出，栈的最基本的特征是LIFO（Last In First Out），因此栈又被称为后进先出的线性表。
2.栈的基本操作
InitStack(&S)--------------构造一个空栈
IsEmpty:判断栈是否为空
ClearStack：清空栈
StackLength：栈S的元素个数，即栈的长度
GetTop：获取栈顶元素
Push：插入新的元素
Pop：删除栈顶元素
3.java.util.Stack源码解析
1）数据结构：利用Vector（动态数组）完成后进先出的操作
2）基本方法：
//初始化一个长度为10 的数组
构造器 public Stack()：
//放入新元素到栈顶
public E push(E item){
//按序更新数组元素（计数器判断最后更新数组元素的索引）
addElement(item);
return item;
}
/**
*1.如果由于新增的元素导致数组的长度不够，则把原来的数组尺寸翻倍，并拷贝老数组元素到新的数组
*/
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
//pop栈顶元素
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
4.java.util.stack的缺点
上述源码分析我们知道，Stack利用Vector动态数组实现了后进先出的栈的基本功能，但是数组有下列缺陷：
(1)当数组默认的容量发生改变时,原有的元素需要经过copy到新的数组中,因此pop、push的性能会有较大降低；
(2)这个类是java.util.Vector的子类，由于是继承stack就会将父类的方法继承过来
如：add(int index,E element)等（具体见Vector的API说明）。这个破坏了stack约定的规则（只能从栈顶进，栈顶出）。
所以SUN公司自己也给出的解释就是不要轻易用这个类。
(3)这个大概就是为了保持兼容性，积重难返，只能将错就错了,不能修改了
5.实现自己的Stack类
数组的缺点是，当数组长度发生变化时，原有的元素需要经过copy到新的数组中，这样性能有较大的损耗，
而链表最大的优点是插入和删除的性能非常好，Java提供了现成的双向链表类java.util.LinkedList，通过它可以快速编写自己的Stack程序，源码如下：
public class Stack<E>{
LinkedList<E> list;
public Stack(){
list = new LinkedList();
}
public E pop(){
return list.removeLast();
}
public void push(E o){
list.add(o);
}
public E getTop(){
return list.getLast();
}
public boolean isEmpty(){
return list.size()==0;
}
public int size(){
return list.size();
}
public static void main(String[] args) {
Stack stack = new Stack();
stack.push("bottom");
stack.push("middle");
stack.push("top");
System.out.println(stack.isEmpty());
System.out.println(stack.getTop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
}
}
并发栈ConcurrentStack<E>
并发栈代码：
package study.tune.system.concurrent;
/**
*
*/
import java.util.concurrent.atomic.AtomicReference;
/**
* 使用Treiber算法实现Stack：基于CAS以及AtomicReference。
*
* @author yangwm Aug 25, 2010 10:50:17 AM
* @author ajian005@gmail.com
*/
public class ConcurrentStack<E> {
AtomicReference<Node<E>> head = new AtomicReference<Node<E>>();
public void push(E item) {
Node<E> newHead = new Node<E>(item);
Node<E> oldHead;
do {
oldHead = head.get();
newHead.next = oldHead;
} while (!head.compareAndSet(oldHead, newHead));
}
public E pop() {
Node<E> oldHead;
Node<E> newHead;
do {
oldHead = head.get();
if (oldHead == null) {
return null;
}
newHead = oldHead.next;
} while (!head.compareAndSet(oldHead, newHead));
return oldHead.item;
}
static class Node<E> {
final E item;
Node<E> next;
public Node(E item) {
this.item = item;
}
}
}
并发栈测试用例：
package study.tune.system.concurrent;
/**
*
*/
import java.util.Stack;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.CyclicBarrier;
/**
* 基准测试：Treiber算法实现Stack、同步实现的Stack
*
* @author yangwm Aug 25, 2010 11:36:14 AM
* @author ajian005@gmail.com
*/
public class StackBenchmark {
public static void main(String[] args) throws Exception {
StackBenchmark stackBenchmark = new StackBenchmark();
stackBenchmark.run();
}
private Stack<String> stack = new Stack<String>();
private ConcurrentStack<String> concurrentStack = new ConcurrentStack<String>();
private static final int THREAD_COUNT = 300;
private CountDownLatch latch = new CountDownLatch(THREAD_COUNT);
private CyclicBarrier barrier = new CyclicBarrier(THREAD_COUNT);
public void run() throws Exception {
StackTask stackTask = new StackTask();
long beginTime = System.currentTimeMillis();
for (int i = 0; i < THREAD_COUNT; i++) {
new Thread(stackTask).start();
}
latch.await();
long endTime = System.currentTimeMillis();
System.out.println("Stack consume Time: " + (endTime - beginTime) + " ms");
latch = new CountDownLatch(THREAD_COUNT);
barrier = new CyclicBarrier(THREAD_COUNT);
ConcurrentStackTask concurrentStackTask = new ConcurrentStackTask();
beginTime = System.currentTimeMillis();
for (int i = 0; i < THREAD_COUNT; i++) {
new Thread(concurrentStackTask).start();
}
latch.await();
endTime = System.currentTimeMillis();
System.out.println("ConcurrentStack consume Time: " + (endTime - beginTime) + " ms");
}
class StackTask implements Runnable {
@Override
public void run() {
try {
barrier.await();
} catch (Exception e) {
e.printStackTrace();
}
for (int i = 0; i < 10; i++) {
stack.push(Thread.currentThread().getName());
stack.pop();
}
latch.countDown();
}
}
class ConcurrentStackTask implements Runnable {
@Override
public void run() {
try {
barrier.await();
} catch (Exception e) {
e.printStackTrace();
}
for (int i = 0; i < 10; i++) {
concurrentStack.push(Thread.currentThread().getName());
concurrentStack.pop();
}
latch.countDown();
}
}
}
/*
Stack consume Time: 94 ms
ConcurrentStack consume Time: 63 ms
Stack consume Time: 78 ms
ConcurrentStack consume Time: 62 ms
*/
参考：http://www.ibm.com/developerworks/java/library/j-jtp04186/index.html