Java基础-数据结构之Stack和Queue源码分析

栈和队列基本概念：

栈 (Stack)是一种后进先出(last in first off，LIFO)的数据结构，而队列(Queue)则是一种先进先出 (fisrt in first out，FIFO)的结构。

java栈实现：

我本地是jdk1.6，实现方式是数组，他继承Vector,Vector其实很像ArrayList，只是他在很多关键方法都加了synchronized关键字，导致每次add或者remove都会获取对象锁阻塞。

看一下栈的三个方法：

public E push(E item)，将一个元素push到栈顶

public E push(E item) {
	addElement(item);
	return item;
    }  
  
public synchronized void addElement(E obj) {
	modCount++;
	ensureCapacityHelper(elementCount + 1);//确保长度够，不够就迁移数组扩容
	elementData[elementCount++] = obj;
    }  
private void ensureCapacityHelper(int minCapacity) {
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object[] oldData = elementData;
	    int newCapacity = (capacityIncrement > 0) ?
		(oldCapacity + capacityIncrement) : (oldCapacity * 2);
    	    if (newCapacity < minCapacity) {
		newCapacity = minCapacity;
	    }
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }  

整体实现还是比较简单，没有太多需要说明的，需要注意的是他的底层数据结构是数组实现的，另外一种实现是链表。

public synchronized E pop() 

public synchronized E peek()

两个方法唯一的差别就是peek只取不删，pop取了之后删掉，看了源码你会很清楚，另外，我们pop和peek方法都是synchronized修饰的，为啥push没有呢？其实你看他的实现，其实vector的addElement就是synchronized方法修饰的，其实他们都是线程安全的，看实现：

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 synchronized E elementAt(int index) {
	if (index >= elementCount) {
	    throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
	}
        return (E)elementData[index];
    }   
public synchronized void removeElementAt(int index) {
	modCount++;
	if (index >= elementCount) {
	    throw new ArrayIndexOutOfBoundsException(index + " >= " +
						     elementCount);
	}
	else if (index < 0) {
	    throw new ArrayIndexOutOfBoundsException(index);
	}
	int j = elementCount - index - 1;
	if (j > 0) {
	    System.arraycopy(elementData, index + 1, elementData, index, j);
	}
	elementCount--;
	elementData[elementCount] = null; /* to let gc do its work */
    } 

我们可以看到，peek是找到length-1索引处的值，就是从后往前取，而pop方法则调用peek，只是在取到数据之后调用了remove方法，通过索引去快速定位并删除。

再来一个例子演示一下：

private static void stackTest() {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(6);
		stack.push(5);
		stack.push(4);
		stack.push(3);
		System.out.println(stack.peek());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
}

可以看到结果：

Java队列实现：

队列是一种先进先出的数据结构，他一般用于多线程的执行队列，他的底层实现也有两种，一种是数组方式，一种是链表方式，由于栈是由数组实现。

先来个例子热热身：

private static void queueTest() {
		Queue<Integer> queue =new ArrayBlockingQueue<Integer>(1024*2);
		queue.add(1);
		queue.add(2);
		queue.add(3);
		System.out.println(queue);
		System.out.println(queue.poll());
		System.out.println(queue);
		System.out.println(queue.peek());
		System.out.println(queue);
}

结果：

可以看出，peek方法依然只是取不删除，poll取出并删除。

看一下类图

画了这么多集合的类图，我发现每个数据结构都是一个接口，然后下面有一个抽象父类实现接口的部分方法，然后具体的每个数据结构都继承这个父类，而且每个集合数据结构的父接口都是Collection，而Collection继承Iterator接口。这就是传说中的集合框架。

看一下方法：

boolean add(E e)

boolean offer(E e)

public boolean add(E e) {
	return super.add(e);
    }
public boolean add(E e) {
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }   
public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            if (count == items.length)
                return false;
            else {
                insert(e);
                return true;
            }
        } finally {
            lock.unlock();
        }
    }  
private void insert(E x) {
        items[putIndex] = x;
        putIndex = inc(putIndex);
        ++count;
        notEmpty.signal();
    }

我们可以看到add的实现就是调用了offer，两个都不能插入null，不一样的是add失败会抛异常，offer插入前检查容量返回false。他会先检查null，还需要知道的是这里采用了和vector不一样的锁方式，采用了重进锁，和ConcurrentHashMap的put和remove方法使用了一样的并发机制，后面专门研究一下锁，这里只需要知道ArrayBlockingQueue是线程安全的。

public E poll()

public E take()

 public E peek()

public E poll() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            if (count == 0)
                return null;
            E x = extract();
            return x;
        } finally {
            lock.unlock();
        }
public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            try {
                while (count == 0)
                    notEmpty.await();
            } catch (InterruptedException ie) {
                notEmpty.signal(); // propagate to non-interrupted thread
                throw ie;
            }
            E x = extract();
            return x;
        } finally {
            lock.unlock();
        }
    }
public E peek() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return (count == 0) ? null : items[takeIndex];
        } finally {
            lock.unlock();
        }
    }
private E extract() {
        final E[] items = this.items;
        E x = items[takeIndex];
        items[takeIndex] = null;
        takeIndex = inc(takeIndex);
        --count;
        notFull.signal();
        return x;
    }	
final int inc(int i) {
        return (++i == items.length)? 0 : i;
    }

poll翻译过来是“民意调查”，peek翻译为“偷看”，take有“取”的含义，extract有”提取“的意思，我们再看源码，他们都有取出的含义，具体区别：

peek只取不删，

take和poll都调用extract方法取出元素，并且将takeIndex向后移动一位，虽然没有将元素置空，但是该元素已经不再数组的处理范围内了，他们唯一不一样的地方就是使用锁的方式不同：

poll加锁时候调用lock.lock

take加锁时候调用lock.lockInterruptibly

lock 与 lockInterruptibly比较区别在于：
lock 优先考虑获取锁，待获取锁成功后，才响应中断。
lockInterruptibly 优先考虑响应中断，而不是响应锁的普通获取或重入获取。ReentrantLock.lockInterruptibly允许在等待时由其它线程调用等待线程的Thread.interrupt方法来中断等待线程的等待而直接返回，这时不用获取锁，而会抛出一个InterruptedException。 ReentrantLock.lock方法不允许Thread.interrupt中断,即使检测到Thread.isInterrupted,一样会继续尝试获取锁，失败则继续休眠。只是在最后获取锁成功后再把当前线程置为interrupted状态,然后再中断线程。

网上找了一些例子：

public static void main(String[] args) throws InterruptedException {
		final Lock lock = new ReentrantLock();
		lock.lock();
		Thread.sleep(1000);
		Thread t1 = new Thread(new Runnable() {
			@Override
			public void run() {
//				 lock.lock();
				try {
					lock.lockInterruptibly();
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
				System.out.println(Thread.currentThread().getName() + " interrupted.");
			}
		});
		t1.start();
		Thread.sleep(1000);
		t1.interrupt();
		Thread.sleep(5000);
		System.out.println("aaa");
	}

执行之后可以稍微清楚的了解他们的差别，就是lock会等待着，当中断的时候还是继续等待，但是lockInterruptibly当检测到中断之后会抛出一个异常。