时间：   |   分类：     |   阅读： 121 字 ~1分钟

双端队列Deque（全名double-endedqueue）是一种数据结构，可在双端队列的两端插入、获取或删除元素。队列和栈可以认为是双端队列的特列。 JDK7中的双端队列Deque实现

Deque常用的方法：

First Element (Head)Last Element (Tail)
Throws exceptionSpecial valueThrows exceptionSpecial value
InsertaddFirst(e)offerFirst(e)addLast(e)offerLast(e)
RemoveremoveFirst()pollFirst()removeLast()pollLast()
ExaminegetFirst()peekFirst()getLast()peekLast()

Deque扩展了Queue接口，当Deque用作FIFO队列时，元素从双端队列队尾加入，从队首移出。从Queue接口继承的方法等同于Deque如下方法：

Queue MethodEquivalent Deque Method
add(e)addLast(e)
offer(e)offerLast(e)
remove()removeFirst()
poll()pollFirst()
element()getFirst()
peek()peekFirst()

Deques也可作为LIFO栈。该接口应该优先于遗留的Stack类使用。当双端队列用作栈时，元素从队首入栈和出栈。Stack方法等同与Deque如下方法：

Stack MethodEquivalent Deque Method
push(e)addFirst(e)
pop()removeFirst()
peek()peekFirst()
注意：当deque用作队列或堆栈时，peek方法也可正常工作，都从deque起始位置移除元素。

JDK6加入的Deque实现

LinkedList: 一个基于链接节点实现的无界双端队列。允许null元素。 ArrayDeque: 一个基于可变长度数组实现的无界双端队列。不允许null元素。

就效率而言，ArrayDeque在两端添加或删除元素时比LinkedList更高效。ArrayDeque用作栈时比Stack更快，用作队列时比LinkedList更快。 LinkedList实现比ArrayDeque实现更复杂，耗费更多的内存。当遍历双端列表时删除当前元素，LinkedList比ArrayDeque更高效。 继承BlockingQueue的BlockingDeque接口及其实现LinkedBlockingDeque：一个基于链接节点实现的可选有界双端队列。如果LinkedBlockingDeque在构造时没有设定容量大小，添加元素永远不会有阻塞队列的等待（至少在其中有Integer.MAX_VALUE元素之前不会）。 LinkedBlockingDeque实现采用一个独占锁，所有对队列的操作都进行了锁保护，因而很好的支持双向阻塞的特性。缺点是由于独占锁，所以不能同时进行两个操作，这样性能上就大打折扣。 LinkedBlockingDeque实现具有显对低的开销及相对低的可扩展性。如果仅需要FIFO队列功能，最好使用LinkedBlockingQueue，LinkedBlockingQueue具有相同的开销但是有更好的伸缩性(例如很多线程竞争时保持更好的性能)。 深入浅出 Java Concurrency (24): 并发容器 part 9 双向队列集合 Deque
深入浅出 Java Concurrency (25): 并发容器 part 10 双向并发阻塞队列 BlockingDeque

JDK7加入的Deque实现

ConcurrentLinkedDeque：一个基于链接节点实现的无界无阻塞双端队列。收集关于队列大小的信息会很慢，需要遍历队列。 ConcurrentLinkedDeque具有跟LinkedBlockingDeque相反的表现：相对高的开销及很好的可伸缩性（使用CAS操作进行非堵塞操作，减少了锁的开销，避免序列化瓶颈）。 [concurrency-interest] BlockingDeque and revised Deque

Deque应用：回文（Palindrome）检查

Deque的应用不是很多，很容易使用双端队列解决的一个有趣问题是经典的回文问题。回文是正着读和倒着读都一样的字符串，例如radar、toot和madam。 回文检查方案是采用Deque存储字符串的字符，将字符串中的字符从左到右插入Deque尾部，则deque头部将持有字符串的首字符，deque尾部将持有字符串的末字符。然后从Deque两端移出字符进行比较，直到Deque内字符数为0或1为止。 JDK7中的双端队列Deque实现

public class PalindromeChecker {

  public static boolean palchecker(String str) {
    if(str==null || str.isEmpty())
      return false;
    
    ArrayDeque aDeque = new ArrayDeque (str.length()); 
    
    for(int i=0;i
      char ch = str.charAt(i);
      aDeque.addLast(new Character(ch));
    }
    
    boolean res = true;
    while (aDeque.size()>1 && res) {
      Character first = aDeque.removeFirst();
          Character last = aDeque.removeLast();
          if(!first.equals(last))
            res = false;
    }
    
    return res;
  }
  
  public static void main(String[] args) {
    System.out.println(palchecker("lsdkjfskf"));
    System.out.println(palchecker("radar"));
  }
}
0%