数据结构——队列(Queue)详解

1.队列（Queue）
1.1概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)的性质

入队列：进行插入操作的一端称为队尾(Tail/Rear)

出队列：进行删除操作的一端称为队头(Head/Front)

2 队列的使用
在Java中，Queue是个接口，底层是通过链表实现的，在实例化Queue时，必须实例化LinkedList对象，因为LinkedList实现了Queue接口

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

1.3 队列模拟实现（双列表实现）

public class MyQueue {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode first;public ListNode last;//尾插public void offer(int val) {ListNode node = new ListNode(val);if(first == null) {first = last = node;}else {node.prev = last;last.next = node;last = last.next;}}//头删public int poll() {//队列为空if(first == null) {return -1;}int ret = first.val;//队列只有一个节点if(first.next == null) {first = last = null;}else {//队列有多个节点first = first.next;first.prev = null;}return ret;}//查看队头元素public int peek() {if(first == null) {return -1;}return first.val;}//判断队列是否为空public boolean isEmpty() {return first == null;}
}