Java双端队列Deque_java 双端队列

1. Deque有三种用途：
   1）普通队列(一端进另一端出):
   Queue queue = new LinkedList()或Deque deque = new LinkedList()
   2）双端队列(两端都可进出)
   Deque deque = new LinkedList()
   3）堆栈
   Deque deque = new LinkedList()
   Deque堆栈操作方法：push()、pop()、peek()。

2. 接口分析
   addFirst(): 向队头插入元素，如果元素为空，则发生NPE(空指针异常)
   addLast(): 向队尾插入元素，如果为空，则发生NPE
   offerFirst(): 向队头插入元素，如果插入成功返回true，否则返回false
   offerLast(): 向队尾插入元素，如果插入成功返回true，否则返回false
   removeFirst(): 返回并移除队头元素，如果该元素是null，则发生NoSuchElementException
   removeLast(): 返回并移除队尾元素，如果该元素是null，则发生NoSuchElementException
   pollFirst(): 返回并移除队头元素，如果队列无元素，则返回null
   pollLast(): 返回并移除队尾元素，如果队列无元素，则返回null
   getFirst(): 获取队头元素但不移除，如果队列无元素，则发生NoSuchElementException
   getLast(): 获取队尾元素但不移除，如果队列无元素，则发生NoSuchElementException
   peekFirst(): 获取队头元素但不移除，如果队列无元素，则返回null
   peekLast(): 获取队尾元素但不移除，如果队列无元素，则返回null
   pop(): 弹出栈中元素，也就是返回并移除队头元素，等价于removeFirst()，如果队列无元素，则发生NoSuchElementException
   push(): 向栈中压入元素，也就是向队头增加元素，等价于addFirst()，如果元素为null，则发生NPE，如果栈空间受到限制，则发生IllegalStateException

3. 实现
   ArrayDeque: 基于数组实现的线性双向队列，通常作为栈或队列使用，但是栈的效率不如LinkedList高。
   LinkedList: 基于链表实现的链式双向队列，通常作为栈或队列使用，但是队列的效率不如ArrayQueue高。

private static void usingAsQueue() {
        Deque<Integer> queue=new ArrayDeque<>();
        System.out.println("队列为空:"+queue.isEmpty());   //判断队列是否为空
        queue.addLast(12);   //添加元素
        System.out.println("队列为空:"+queue.isEmpty());   //判断队列是否为空
        System.out.println(queue.peekFirst());   //获取队列首部元素
        System.out.println(queue.pollFirst());   //获取并移除栈顶元素
        System.out.println("队列为空:"+queue.isEmpty());   //判断队列是否为空
 }

private static void usingAsStack() {
        //作为栈使用
        Deque<Integer> stack=new LinkedList<>();
        System.out.println("栈为空:"+stack.isEmpty());   //判断栈是否为空
        stack.addFirst(12);
        System.out.println("栈为空:"+stack.isEmpty());   //判断栈是否为空
        System.out.println(stack.peekFirst());   //获取栈顶元素
        System.out.println(stack.pollFirst());   //获取并移除栈顶元素
        System.out.println("栈为空:"+stack.isEmpty());   //判断栈是否为空
        System.out.println("============================================");

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21