Java数据结构————队列

一 、队列

在Java中，Queue是个接口，底层是通过链表实现的。

只允许在一端进行插入数据操作，
在另一端进行删除数据操作的特殊线性表，
队列具有先进先出FIFO(First In First Out) 。

入队列：
进行插入操作的一端称为队尾（Tail/Rear）。

出队列：
进行删除操作的一端称为队头（Head/Front）。

二 、队列的常用方法

Queue是个接口，
在实例化时必须实例化LinkedList的对象，
因为LinkedList实现了Queue接口。

public static void main(String[] args) {
    Queue q = new LinkedList<>();
    q.offer(1);
    q.offer(2);
    q.offer(3);
    q.offer(4);
    q.offer(5);                  // 从队尾入队列
    System.out.println(q.size());
    System.out.println(q.peek());  // 获取队头元素
    
    q.poll();
    System.out.println(q.poll());  // 从队头出队列，并将删除的元素返回
    
    if(q.isEmpty()){
        System.out.println("队列空");
    }else{
        System.out.println(q.size());
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三 、 队列的模拟实现

四 、 循环队列

循环队列通常使用数组实现。

五 、 双端队列 (Deque)

Deque是一个接口，使用时必须创建LinkedList的对象。

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，
deque 是 “double ended queue” 的简称。
元素可以从队头出队和入队，也可以从队尾出队和入队。