java中的栈和队列

一、队列的简单介绍

队列是一种遵循先进先出原则的数据结构，一般会有一个对头和一个对尾,只能在对头取出元素，在队尾添加元素。

在上边的图中元素4最先进入队列,所以元素4最先从队头取出

二、java中的队列接口

2.1 Queue

java中给出了一个接口java.util.Queue 来定义了队列基本的操作方法,这些方法根据功能可以分为3类,插入，取出,查看

其中add和offer都是往队尾添加元素的方法，区别是当队列容量已满不能添加新元素时

add方法会抛出IllegalStateException

offer方法不抛出异常会返回false。

remove和poll都是从队头移出(取出)元素的方法，区别是当队列中没有元素时remove会抛出异常NoSuchElementException ,poll会返回null

element和peek都是返回队列头部的元素但不把它从队列中删除,这是和remove方法的区别，同样的它们俩当队列中没有元素时一个会抛出异常，一个会返回false。

2.2 Deque

java.util.Deque 这是java中定义的一个双向队列接口,双向的意思就是在这个队列的两端都可以进行插入和取出元素的操作。

这些方法被分为了操作头和操作尾两大类，同时也可以按抛异常/返回特殊值分为两大类。

当然双向队列是可以被当做单向队列使用的,只需要按队尾进对头出的原则调用方法就行，因为Deque是Queue 的子类，所以队列接口中的方法它都有，方法间是有对应关系的。

当把Deque当做单向队列来使用时更推荐使用右边的方法来完成操作。

当然对于双向队列,你只要从一端添加，从另一端移出，它就是被当做单向队列在使用,既可以尾进头出,也可以头进尾出,这个时候都是单向队列

三、java中队列的常见实现类

ArrayDeque,这是一个基于数组的双向队列实现，这个队列没有容量限制，放置元素时会自动扩容(容量*2),所以可以说是一个无界队列，但实际上一个容器的容量不可能无限大,否则会撑爆内存，所以扩容方法doubleCapacity

中做了限制，因为源码中容量*2是通过把原来的容量左移一位来实现加倍的,所以当这个数字特别大，左移后超出int的上限就会变成负数,这个状态就是容量上限。

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 = a;
        head = 0;
        tail = n;
}

LinkedList 是一个基于链表的双向队列实现，当然它同时也是List接口的实现。它也是一个无界队列，因为是基于链表实现的，所以容量理论上是无限的,但实际当然受限于内存的大小。

LinkedBlockingQueue 基于链表实现, 这虽然是一个阻塞队列，但也可以被当做普通队列使用，它是一个有界队列，当创建时不指定容量，则默认的容量是Integer.MAX_VALUE

ArrayBlockingQueue 基于数组实现 这虽然是一个阻塞队列，但也可以被当做普通队列使用，它是一个有界队列，创建时必须指定容量.

四、java中的栈

栈是一种遵循先入后出的数据结构,先进入的元素被压到栈底最后才能弹出。

java提供了一个Stack 类来描述栈，但实际上双向队列Deuque 就可以被当做栈使用,只需要按先入后出的元素调用方法

push是入栈(压入栈底),pop是出栈(返回栈顶并移出),peek是返回栈顶(不移除)的元素，都可以用Deque的方法代替。