队列 Queue

• 队列是一种特殊的线性表，只能在头尾两端操作
• 队尾（rear）: 只能从队尾添加元素，即 enQueue，入队
• 队头（front）: 只能从队头移除元素，即 deQueue，出队
• 队列遵循先进先出的原则，First In First Out，FIFO

实现队列

• 队列的内部实现可以使用动态数组或双向链表实现，但是优先使用双向链表 LinkedList，因为队列主要是操作头尾元素
• 官方 JDK 源码的 Queue 是一个接口，由 LinkedList 实现了该接口

import java.util.LinkedList;
import java.util.List;

public class Queue<E> {
    private List<E> list;

    public Queue() {
        list = new LinkedList<>();
    }

    public int size() {
        return list.size();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    // 入队，将元素添加至链表尾部
    public void enQueue(E ele) {
        list.add(ele);
    }

    // 出队，删除并返回链表的头节点元素
    public E deQueue() {
        return list.remove(0);
    }
    
    // 获取队头元素但不出队，获取链表的头节点元素
    public E front() {
        return list.get(0);
    }
}

双端队列 Deque

• 双端队列是在队头和队尾都可以添加、删除元素的特殊队列

实现双端队列

import java.util.LinkedList;
import java.util.List;

public class Deque<E> {
    private List<E> list;

    public Deque() {
        list = new LinkedList<>();
    }

    public int size() {
        return list.size();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
    
    // 从队头入队
    public void enQueueFront(E ele) {
        list.add(0,ele);
    }
    
    // 从队尾入队
    public void enQueueRear(E ele) {
        list.add(ele);
    }
    
    // 从队头出队
    public E deQueueFront() {
        return list.remove(0);
    }
    
    // 从队尾出队
    public E deQueueRear() {
        return list.remove(list.size()-1);
    }
    
    // 获取队头元素
    public E front() {
        return list.get(0);
    }
    
    // 获取队尾元素
    public E rear() {
        return list.get(list.size()-1);
    }
}

参考

• 恋上数据结构与算法（第一季）
• 小码哥《恋上数据结构与算法》笔记（六）：队列