queue,deque

╰半夏微凉° 2022-07-21 02:22 163阅读 0赞

**from：http://uule.iteye.com/blog/2095650?utm\_source=tuicool**

**1、Queue**

**[API][]**

在java5中新增加了java.util.Queue接口，用以支持队列的常见操作。该接口扩展了java.util.Collection接口。

Java代码

1.  **public** **interface** Queue<E>   
2.      **extends** Collection<E>

除了基本的 Collection 操作外，队列还提供其他的插入、提取和检查操作。

每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）**。使用或者！**

![0a3af09c-84c1-3192-a396-788778793770.jpg][]

队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。

**在 FIFO 队列中，所有的新元素都插入队列的末尾，移除元素从队列头部移除。**

Queue使用时要**尽量避免Collection的add()和remove()方法**，**而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常**。 如果要使用前端而不移出该元素，使用element()或者peek()方法。

![点击查看原始大小图片][6c5cd3f1-9cb8-3af5-8be6-558e880fb143.jpg]

offer 方法可插入一个元素，否则返回 false。这与 Collection.add 方法不同，该方法只能通过抛出未经检查的异常使添加元素失败。

remove() 和 poll() 方法可移除和返回队列的头。到底从队列中移除哪个元素是队列排序策略的功能，而该策略在各种实现中是不同的。remove() 和 poll() 方法仅在队列为空时其行为有所不同：remove() 方法抛出一个异常，而 poll() 方法则返回 null。

element() 和 peek() 返回，但不移除，队列的头。

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。

值得注意的是LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

Java代码   ![收藏代码][icon_star.png]

1.  **import** java.util.Queue;    
2.  **import** java.util.LinkedList;    
3.    
4.  **public** **class** TestQueue \{    
5.      **public** **static** **void** main(String\[\] args) \{    
6.          Queue<String> queue = **new** LinkedList<String>();    
7.          queue.offer("Hello");    
8.          queue.offer("World!");    
9.          queue.offer("你好！");    
10.         System.out.println(queue.size());    
11.         String str;    
12.         **while**((str=queue.poll())!=**null**)\{    
13.             System.out.print(str);    
14.         \}    
15.         System.out.println();    
16.         System.out.println(queue.size());    
17.     \}    
18. \}

3  
HelloWorld!你好！//poll为移出并且获取！！！  
0

eg2:

package com.ljq.test;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class QueueTest {
        public static void main(String[] args) {
            //add()和remove()方法在失败的时候会抛出异常(不推荐)
            Queue<String> queue = new LinkedList<String>();
            //添加元素
            queue.offer("a");
            queue.offer("b");
            queue.offer("c");
            queue.offer("d");
            queue.offer("e");
            for(String q : queue){
                System.out.println(q);
            }
            System.out.println("===");
            System.out.println("poll="+queue.poll()); //返回第一个元素，并在队列中删除
            for(String q : queue){
                System.out.println(q);
            }
            System.out.println("===");
            System.out.println("element="+queue.element()); //返回第一个元素 
            for(String q : queue){
                System.out.println(q);
            }
            System.out.println("===");
            System.out.println("peek="+queue.peek()); //返回第一个元素 
            for(String q : queue){
                System.out.println(q);
            }
            
        }
    }

a  
b  
c  
d  
e  
===  
poll=a  
b  
c  
d  
e  
===  
element=b  
b  
c  
d  
e  
===  
peek=b  
b  
c  
d  
e

**2、Deque**

[API][API 1]

Java代码   ![收藏代码][icon_star.png]

1.  **public** **interface** Deque<E>  
2.      **extends** Queue<E>

**一个线性 collection，支持在两端插入和移除元素。**

名称 deque 是“**double ended queue（双端队列）**”的缩写，通常读为“deck”。

大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

![b1956624-3f28-312c-808a-301e67059ce8.jpg][]

![1354809676_3123.png][]

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。因为此接口**继承了队列接口Queue**，所以其每种方法也存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

**a、****在将双端队列用作队列时，将得到 FIFO（先进先出）行为**。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：

![f769ea83-1a83-3bec-84df-52342cbe00b8.jpg][]

**b、****用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类**。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

![610121eb-2298-36a9-918a-73cdaa085df9.jpg][]

**eg:Deque 实现堆栈**

**   **

import java.util.ArrayDeque;
    import java.util.Deque;
     
    public class IntegerStack {
      private Deque<Integer> data = new ArrayDeque<Integer>();
     
      public void push(Integer element) {
        data.addFirst(element);
      }
     
      public Integer pop() {
        return data.removeFirst();
      }
     
      public Integer peek() {
        return data.peekFirst();
      }
     
      public String toString() {
        return data.toString();
      }
     
      public static void main(String[] args) {
        IntegerStack stack = new IntegerStack();
        for (int i = 0; i < 5; i++) {
          stack.push(i);
        }
        System.out.println("After pushing 5 elements: " + stack);
     
        int m = stack.pop();
        System.out.println("Popped element = " + m);
     
        System.out.println("After popping 1 element : " + stack);
     
        int n = stack.peek();
        System.out.println("Peeked element = " + n);
        System.out.println("After peeking 1 element : " + stack);
      }
    }

**After pushing 5 elements: \[4, 3, 2, 1, 0\]  
Popped element = 4  
After popping 1 element : \[3, 2, 1, 0\]  
Peeked element = 3  
After peeking 1 element : \[3, 2, 1, 0\]**

[API]: http://dlc.sun.com.edgesuite.net/jdk/jdk-api-localizations/jdk-api-zh-cn/publish/1.6.0/html/zh_CN/api/java/util/Queue.html#peek%28%29
[0a3af09c-84c1-3192-a396-788778793770.jpg]: /images/20220720/cf758425316f41f2bae8f373ec5b64f6.png
[6c5cd3f1-9cb8-3af5-8be6-558e880fb143.jpg]: /images/20220720/e6f462b2829b4386b57d13f20fc615af.png
[icon_star.png]: /images/20220720/7249ae8909f2486b9ec5170276c58711.png
[API 1]: http://dlc.sun.com.edgesuite.net/jdk/jdk-api-localizations/jdk-api-zh-cn/publish/1.6.0/html/zh_CN/api/java/util/Deque.html
[b1956624-3f28-312c-808a-301e67059ce8.jpg]: /images/20220720/8abea60496c54c8fa6616e78895a8007.png
[1354809676_3123.png]: https://img-my.csdn.net/uploads/201212/07/1354809676_3123.png
[f769ea83-1a83-3bec-84df-52342cbe00b8.jpg]: /images/20220720/3a1e61203d734a3ebbdaf7c1679a9fca.png
[610121eb-2298-36a9-918a-73cdaa085df9.jpg]: /images/20220720/f5c10947a48e47eea4678ce13e9ac40b.png

queue,deque

发表评论取消回复

还没有评论，来说两句吧...

相关阅读