Java集合之队列和栈

队列Queue

Queue是Java中的一个接口，继承自Collection接口。

public interface Queue
    
      extends Collection
     
       {    boolean add(E e); //向队尾添加元素    boolean offer(E e); //向队尾添加元素    E remove();  //移除队头元素    E poll(); //移除队头元素    E element();//返回队头元素，但不移除队头元素。如果队列是空的，抛出异常    E peek(); 返回队头元素，但不移除队头元素。如果队列是空的，返回null}
     
    

offer方法和add方法的区别：

offer方法——{

true} if the element was added to this queue, else {

false}

add方法——<tt>true</tt> if this collection changed as a result of the call（如果添加元素成功，则返回true，否则，不会返回false，而是抛出异常）（返回值总是true）

已知的子接口和实现类

All Known Subinterfaces:

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All Known Implementing Classes:

AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

Queue本身是一种先入先出的模型(FIFO)，和我们日常生活中的排队模型很类似。根据不同的实现，他们主要有数组和链表两种实现形式。

数组形式：

链表形式：

双端队列Deque

继承自接口Queue。是一个双端队列，双端队列（deque，全名double-ended queue）是一种具有队列和栈性质的数据结构。双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两边进行。

双端队列可以在队列任意一端入队和出队。此外，经常还会有一个查看（Peek）操作，返回该端的数据而不将其出队。

package java.util;public interface Deque
    
      extends Queue
     
       {       void addFirst(E e);    void addLast(E e);    boolean offerLast(E e);    E removeFirst();    E removeLast();    E pollFirst();    E pollLast();    E getFirst();    E getLast();    E peekFirst();    E peekLast();    boolean removeFirstOccurrence(Object o);    boolean removeLastOccurrence(Object o);    // *** Queue methods ***    boolean add(E e);    boolean offer(E e);    E remove();    E poll();    E element();    E peek();    // *** Stack methods ***    void push(E e);    E pop();        // *** Collection methods ***    boolean remove(Object o);    boolean contains(Object o);    public int size();    Iterator
      
        iterator();    Iterator
       
         descendingIterator();}
       
      
     
    

已知的子接口和实现类

All Known Subinterfaces:

BlockingDeque<E>

All Known Implementing Classes:

ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList

阻塞队列BlockingQueue

详见：

阻塞双端队列BlockingDeque

这既是一个双端队列，具有双端队列的操作，也具有阻塞队列的特性

栈Stack

同步容器Vector在java 中可以实现自动增长的对象数组

栈是一种先进后出的模式。由源码可见，Java栈Stack继承自同步容器Vector

package java.util;public class Stack
    
      extends Vector
     
       {    /**     * Creates an empty Stack.     */    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;    }        private static final long serialVersionUID = 1224463164541339165L;}
     
    

=====END====