4.队列与双端队列
2016-08-07 本文已影响1224人
KaelQ
1.队列概述
-
队列(queue)是一种是相对于栈的一种数据结构，它是先进先出(First In First Out)。
它只可以在尾部添加元素。
队列
- 双端队列(deque double ended queue（双端队列）)是一种相对于队列的一种数据结构。它可以在尾部和头部插入、移除和获取。
双端队列
2.队列方法
- java.util.Queue接口，用以支持队列的常见操作。该接口扩展了java.util.Collection接口。
| 方法 | 抛出异常 | 返回值 |
|---|---|---|
| 插入 | add() | offer() |
| 删除 | remove() | poll() |
| 查询 | element() | peek() |
- java.util.Deque接口，用以支持双端队列的常见操作。该接口扩展了java.util.Queue接口。
|方法|头部抛出异常|尾部抛出异常 |头部返回值|尾部返回值|
|-|-|-|
|插入|addFirst()|offerFirst()|addLast()|offerLast()|
|删除|removeFirst()|pollFirst()|removeLast()|pollLast()|
|查询|getFirst()|peekFirst()|getLast()|peekLast()|
- LinkedList是一个继承于AbstractSequentialList的双向链表。
使用LinkedList实现Queue接口来表示队列。
使用LinkedList实现Deque接口来表示双向队列。 - Queue<String>queue=newLinkedList<String>();
- Deque<String> deque = new LinkedList<String>();
3.有意思的例子
-
怎样用栈来实现一个队列？
答：使用两个栈A和B，A栈将数据正常进栈，然后出栈进入B栈，从B栈出来的数据就是队列的数据。
