Queue 和 Deque

通过前面的学习，我们已经了解了List的使用，其中LinkedList除了可以直接当做列表使用之外，还可以当做其他的数据结构使用，可以看到它不仅仅实现了List接口：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{

还实现了 Deque 接口。

Queue 接口

public interface Queue<E> extends Collection<E> {
    //队列的添加操作，是在队尾进行插入（只不过List也是一样的，默认都是尾插）
      //如果插入失败，会直接抛出异常
    boolean add(E e);
 
    //同样是添加操作，但是插入失败不会抛出异常
    boolean offer(E e);
 
    //移除队首元素，但是如果队列已经为空，那么会抛出异常
    E remove();
 
       //同样是移除队首元素，但是如果队列为空，会返回null
    E poll();
 
    //仅获取队首元素，不进行出队操作，但是如果队列已经为空，那么会抛出异常
    E element();
 
    //同样是仅获取队首元素，但是如果队列为空，会返回null
    E peek();
}

应用： 我们可以直接将一个LinkedList当做一个队列来使用：

public static void main(String[] args) {
    Queue<String> queue = new LinkedList<>();   //当做队列使用，还是很方便的
    queue.offer("AAA");
    queue.offer("BBB");
    System.out.println(queue.poll());
    System.out.println(queue.poll());
}

Deque 接口

//在双端队列中，所有的操作都有分别对应队首和队尾的
public interface Deque<E> extends Queue<E> {
    //在队首进行插入操作
    void addFirst(E e);
 
    //在队尾进行插入操作
    void addLast(E e);
        
      //不用多说了吧？
    boolean offerFirst(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);
 
    // *** 队列中继承下来的方法操作是一样的，这里就不列出了 ***
 
    ...
 
    // *** 栈相关操作已经帮助我们定义好了 ***
 
    //将元素推向栈顶
    void push(E e);
 
    //将元素从栈顶出栈
    E pop();
 
 
    // *** 集合类中继承的方法这里也不多种介绍了 ***
 
    ...
 
    //生成反向迭代器，这个迭代器也是单向的，但是是next方法是从后往前进行遍历的
    Iterator<E> descendingIterator();
}

迭代器

分为正向迭代器 .iterator， 和反向迭代器 .descendingIterator

public static void main(String[] args) {
    Deque<String> deque = new LinkedList<>();
    deque.addLast("AAA");
    deque.addLast("BBB");
    
    Iterator<String> descendingIterator = deque.descendingIterator();
    System.out.println(descendingIterator.next());
 
    Iterator<String> iterator = deque.iterator();
    System.out.println(iterator.next());
}
 

应用

可以直接当做栈：

public static void main(String[] args) {
	Deque<String> deque = new LinkedList<>();
	deque.push("AAA");
	deque.push("BBB");
	System.out.prinln(deque.pop());
	System.out.prinln(deque.pop());
}