Java中Queue和Deque接口

我们通过对比两个接口以及实现类包括实现类的常用方式来详细了解Queue和Deque两个接口。

一、Queue和Dqueue

1、Queue以及Deque都是继承与Cellection的接口，Deque是queue的子接口。

2、Queue是单向队列，FIFO

        Deque是双向队列

3、Queue有一个直接子类PriorityQueue。PriorityQueue叫做优先队列，顾名思义，该队列是有序的，该队列内部是一个通过小顶堆维护的二叉树，通过数组实现，多以在插入时会更新小顶堆，取出元素时会取出最小的值。

Deque有两个直接子类：LinkedList和ArrayDeque。ArrayDeque是无初始容量的双端队列，LinkedList则是双向链表。

4、PriorityQueue、LinkedList、ArrayDeque用法比较：

用法：PriorityQueue可以用作堆，根据传入的Comparator实现大小的调整，会是一个很好的选择

用法：

ArrayDeque 通常作为栈或队列使用，但是栈的效率不如LinkedList高。
LinkedList 通常作为栈或队列使用，但是队列的效率不如ArrayQueue高。

5、API对比

（1）、add和offer的区别

• add()：添加元素如果添加成功则返回true，如果队列是满的，则抛出异常
• offer()：添加元素，如果添加成功则返回true，如果队列是满的，则返回false

（2）、remove和poll

• remove()：移除队列头的元素并且返回，如果队列为空则抛出异常
• poll()：移除队列头的元素并且返回，如果队列为空则返回null
• Deque新增了一个pop方法，也是移除队列头的元素并且返回，如果队列为空则抛出异常。

（3）、element和peek

• element()：返回队列头元素但不移除，如果队列为空，则抛出异常
• peek()：返回队列头元素但不移除，如果队列为空，则返回null

因此，推荐使用offer()，移除使用poll()，获取元素使用peek().

代码实现：

Queue：（实现queue同样使用LinkedList类）

public static void test01(){
    Queue<String> queue = new LinkedList<>();
    // add()和remove()方法在失败的时候会抛出异常(不推荐)
    queue.offer("a");
    queue.offer("b");
    queue.offer("c");
    queue.offer("d");
    queue.offer("e");
    queue.add("f");
    //在队列元素为空的情况下，remove() 方法会抛出NoSuchElementException异常，poll() 方法只会返回 null 。
    String first2 = queue.remove();//返回第一个元素，删除
    System.out.println(first2);//a
    String first1 = queue.poll();//返回第一个元素，删除
    System.out.println(first1);//b
    String first = queue.peek();//返回第一个元素，但不删除
    System.out.println(first);//c
    System.out.println(queue);//[c, d, e, f]
    first = queue.element();//返回第一个元素
    System.out.println(first);//c
}

 Deque：（实现双端队列或者栈使用LinkedList和ArrayDeque都可以）

/*实现双端队列*/
public static void test02(){
    Deque<String> deque = new LinkedList<>();
    deque.offer("a");
    deque.offer("b");
    deque.offerFirst("c");//在队列头部进行插入
    System.out.println(deque);//[c, a, b]
    deque.offerLast("d");
    System.out.println(deque);//[c, a, b, d]

    String ret = deque.element();//返回第一个元素
    System.out.println(ret);//c

    ret = deque.getFirst();//返回第一个元素
    System.out.println(ret);//c
    ret = deque.getLast();//返回最后一个元素
    System.out.println(ret);//d

    ret = deque.peek();//返回第一个元素，但不删除
    System.out.println(ret);//c

    ret = deque.peekFirst();//返回第一个元素，但不删除
    System.out.println(ret);//c
    ret = deque.peekLast();//返回最后一个元素，但不删除
    System.out.println(ret);//d

    System.out.println(deque);

    ret = deque.poll();//返回第一个元素，删除
    System.out.println(ret);//c
    System.out.println(deque);//[a, b, d]

    ret = deque.pop();//返回第一个元素，删除
    System.out.println(ret);//a
    System.out.println(deque);//[b, d]

    deque.clear();
    ret = deque.pop();//抛异常
    System.out.println("11111");
    ret = deque.poll();//返回null,但不抛异常
    System.out.println("++"+ret);
    System.out.println("22222");
}

两种数据结构使用的例题：二叉树层序遍历102、二叉树层序遍历的变形（锯齿形层序）103

二叉树层序遍历：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //定义二维数组
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }
        //Queue定义普通队列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            //定义数组（链表）存放每一层的结果
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}

二叉树层序遍历（锯齿形层序）：

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //定义二维数组 存放结果
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        if (root == null) {
            return ans;
        }
        //Queue定义普通队列、FIFO
        Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
        nodeQueue.offer(root);
        boolean isOrderLeft = true;

        while (!nodeQueue.isEmpty()) {
            //Deque定义一个双端队列，用来决定该行的插入顺序
            Deque<Integer> levelList = new LinkedList<Integer>();
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode curNode = nodeQueue.poll();
                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);
                } else {
                    levelList.offerFirst(curNode.val);
                }
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            //将当前行的结果存入二维数组
            ans.add(new LinkedList<Integer>(levelList));
            isOrderLeft = !isOrderLeft;
        }

        return ans;
    }
}

完整测试代码：

/**
 * 二叉树的层序遍历
 */
class cengxu {
    //层序遍历锯齿状
    public List<List<Integer>> levelOrder_juchi(TreeNode root){
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        Queue<TreeNode> nodequeue = new LinkedList<TreeNode>();
        nodequeue.offer(root);
        boolean isleftsort = false;

        while (!nodequeue.isEmpty()){
            Deque<Integer> levelnum = new LinkedList<Integer>();
            int size = nodequeue.size();
            for(int i=0;i<size;i++){
                TreeNode node = nodequeue.poll();
                if(isleftsort){
                    levelnum.addFirst(node.val);
                }else{
                    levelnum.addLast(node.val);
                }
                if(node.left!=null){
                    nodequeue.add(node.left);
                }
                if(node.right!=null){
                    nodequeue.add(node.right);
                }
            }
            res.add(new LinkedList<>(levelnum));
            isleftsort = !isleftsort;
        }
        return res;
    }
    //层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        Queue<TreeNode> nodequeue = new LinkedList<TreeNode>();
        nodequeue.offer(root);

        while (!nodequeue.isEmpty()){
            Queue<Integer> levelnum = new LinkedList<Integer>();
            int size = nodequeue.size();
            for(int i=0;i<size;i++){
                TreeNode node = nodequeue.poll();

                levelnum.offer(node.val);

                if(node.left!=null){
                    nodequeue.add(node.left);
                }
                if(node.right!=null){
                    nodequeue.add(node.right);
                }
            }
            res.add(new LinkedList<>(levelnum));
        }
        return res;

    }
    public static void main(String[] args){
        //写一个二叉树的输入函数
        TreeNode head = new TreeNode(3);
        TreeNode rl = head.addleft(9);
        TreeNode rr = head.addright(20);
        rr.addleft(15);
        rr.addright(7);
        cengxu c = new cengxu();
        List<List<Integer>> res = c.levelOrder(head);
//        List<List<Integer>> res = c.levelOrder_juchi(head);
        System.out.println(res);
        for(int i=0;i<res.size();i++){
            List<Integer> list = res.get(i);
            for(int j=0;j<list.size();j++){
                System.out.println(list.get(j));
            }
        }
    }
}