`
uule
  • 浏览: 6348874 次
  • 性别: Icon_minigender_1
  • 来自: 一片神奇的土地
社区版块
存档分类
最新评论

队列Queue、双端队列Deque

 
阅读更多

注意:这都只是接口而已

 

1、Queue

API

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

 

public interface Queue<E>	
	extends Collection<E>

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

 

每个方法都存在两种形式:一种抛出异常(操作失败时),另一种返回一个特殊值(null 或 false,具体取决于操作)


 

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

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

 

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


 

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来用。

import java.util.Queue;  
import java.util.LinkedList;  

public class TestQueue {  
    public static void main(String[] args) {  
        Queue<String> queue = new LinkedList<String>();  
        queue.offer("Hello");  
        queue.offer("World!");  
        queue.offer("你好!");  
        System.out.println(queue.size());  
        String str;  
        while((str=queue.poll())!=null){  
            System.out.print(str);  
        }  
        System.out.println();  
        System.out.println(queue.size());  
    }  
} 

 

 

2、Deque

API 

public interface Deque<E>
	extends Queue<E>

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

名称 deque 是“double ended queue(双端队列)”的缩写,通常读为“deck”。

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

 

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

 

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


 

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


 。。

 

 

  • 大小: 14.3 KB
  • 大小: 89.2 KB
  • 大小: 35.3 KB
  • 大小: 22.7 KB
  • 大小: 11.8 KB
分享到:
评论
2 楼 Heathcliff 2015-12-22  
这个怎么删评论?
1 楼 Heathcliff 2015-12-22  
public boolean offer(E e) {
        return offerLast(e);
    }


 public boolean offerLast(E e) {
        addLast(e);
        return true;
    }


对于arrayDeque这个返回值除了永真,就是抛出异常不返回,这样返回值还有意义吗?

相关推荐

    算法-数据结构和算法-5-队列和双端队列.rar

    本资源主要聚焦于两种常用的数据结构:队列和双端队列(deque),这些都是编程中不可或缺的部分,尤其是在处理顺序访问和存储的问题时。 首先,队列是一种遵循“先进先出”(FIFO)原则的数据结构。想象一下现实...

    双端队列C++实现 双端队列C++实现

    双端队列(Double-Ended Queue,简称deque)是一种线性数据结构,它允许在队列的两端进行插入和删除操作。在C++标准库中,`std::deque`是内置的双端队列容器,提供了高效且灵活的内存管理。然而,如果你想要自定义一...

    chapter_6_栈、队列和双端队列.zip

    本章节将探讨Python中三种常用的数据结构:栈(Stack)、队列(Queue)和双端队列(Dequeue)。这些数据结构都有其独特的特性和应用场景,理解和掌握它们对于提升编程技能至关重要。 **栈**,又称为后进先出(Last ...

    自定义双端队列

    所谓双端队列(double-ended queue,deque),就是在列表的两端都可以插入和删除数据。 因此它允许的操作有Create、IsEmpty、IsFull、Left、Right、AddLeft、AddRight、DeleteLeft、 DeleteRight。使用循环数组方式...

    双端队列派生类

    双端队列,在基础类上派生 用来实现平移递推滤波数据存储

    vc++中队列deque和queue的使用

    在VC++编程环境中,`deque`(双端队列)和`queue`是两种常用的容器,它们都属于标准模板库(STL)的一部分,用于处理数据的存储和操作。这两个容器在实现队列数据结构时各有特点,适用于不同的场景。在VS2010中,...

    双端队列源代码

    双端队列(Double-Ended Queue,简称deque)是一种数据结构,它允许我们在队列的两端进行插入和删除操作。这种特性使得双端队列在许多算法和数据处理场景中非常有用,比如作为栈的替代品,或者在需要快速访问两端...

    基于python的数据结构代码实现-队列Queue

    Python的`collections.deque`类提供了双端队列的功能,可以更高效地处理队列操作。创建一个`deque`实例,然后使用`append()`添加元素到队尾(右端),使用`popleft()`移除元素并返回队头元素(左端)。 3. **线程...

    详解Python的collections模块中的deque双端队列结构

    Python的collections模块包含了一个高效的数据结构,叫做deque(双端队列)。deque是double-ended queue的缩写,它提供了一种高效的方式来进行两端插入和删除操作,这比Python内置的list结构更为便捷。deque的设计...

    双端队列Deque及Python实现

    双端队列(Deque,全称Double-Ended Queue)是一种线性数据结构,它具有队列的特点,同时允许在队列的两端进行插入和删除操作。这种数据结构的设计使得它在处理某些特定问题时非常高效,例如在需要快速地在两端进行...

    双端队列就是一个两端都是结尾的队列的程序

    双端队列(Deque,Double-ended Queue)是一种特殊的数据结构,它既可以在队列的一端进行元素的插入与删除操作,也可以在队列的另一端进行同样的操作。这种特性使得双端队列比普通的队列更加灵活。根据题目中的描述...

    【课件】3.2.4_双端队列.pdf

    双端队列(Deque, Double-ended Queue)是一种线性数据结构,它允许在两端进行元素的插入和删除操作。与传统的队列相比,双端队列具有更大的灵活性,因为它不仅支持队首(front)的插入和删除,还支持队尾(rear)的插入...

    数据结构笔记:双端队列

    双端队列(deque,double-ended queue),是一种具有队列和栈的性质的数据结构。 双端队列中每一端,都可以进行存入和取出,去其中一段,都像一个栈一样。 存取也只限定在两端,不能在中间 双端队列的实现 通过...

    【实验报告】 线性数据结构的实现与应用_双端队列_逆波兰式_呼叫中心_XAUAT_(原问题自杜克大学C++ Stacks and Queues and List

    本次实验的主要目的是理解和掌握线性数据结构——双端队列(Double-Ended Queue,简称deque)的实现与应用。通过实际编程,加深对双端队列特性的理解,如其在头部和尾部进行插入和删除操作的灵活性。同时,将双端...

    用数组实现的双端队列(类模板)

    双端队列(Double-Ended Queue,简称deque)是一种数据结构,它允许在队列的两端进行插入和删除操作。在C++中,标准库提供了一个名为`deque`的容器,但在这里,我们讨论的是一个自定义实现的基于数组的双端队列类...

    duilie.rar_双端队列

    双端队列(Double-Ended Queue,简称deque)是一种数据结构,它允许在队列的两端进行插入和删除操作。这种特性使得双端队列在许多算法和程序设计中非常实用,比如作为栈的替代,或者在需要快速访问两端元素的场景下...

    python队列queue模块详解

    `_init(maxsize)`内部使用了Python的`collections.deque`双端队列实现,这使得在两端添加或删除元素非常高效。 `queue`模块为了保证线程安全,使用了互斥锁(`mutex`)和条件变量。互斥锁(`self.mutex`)确保任何...

    Python实现的数据结构与算法之双端队列详解

    双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构。双端队列也拥有两端:队首(front)、队尾(rear),但与队列不同的是,插入操作在两端(队首和队尾)都可以进行,删除操作也一样...

    Socket异步通信,线程,双端队列

    双端队列(Double Ended Queue,简称deque)是STL中的一种容器,它支持在两端进行插入和删除操作。相比传统的队列,双端队列提供了更多的灵活性,可以在两端快速地添加或移除元素,这在设计高效的数据结构和算法时...

Global site tag (gtag.js) - Google Analytics