队列

一、定义

队列（Queue）是一种基于先进先出（FIFO，First In First Out）原则的数据结构。在队列中，最先插入的元素最先被移除，而最后插入的元素最后被移除。队列具有入队（Enqueue）和出队（Dequeue）两个基本操作，以及查看队首元素和队尾元素的操作。

二、特点

队列具有以下特点：

1. 先进先出：最先入队的元素会最先出队，形成了先进先出的特性。
2. 限制访问：队列只允许在队首进行出队操作，在队尾进行入队操作，其他位置的元素无法直接访问。
3. 快速操作：由于队列的限制，入队、出队和查看队首元素的操作通常具有常数时间复杂度，即O(1)。

三、实现方式

队列可以通过数组或链表等不同的数据结构来实现（动态数组和链表的一种应用方式）：

1. 数组实现：使用数组来存储队列中的元素，同时使用两个指针来表示队首和队尾的位置。入队操作将元素插入到数组的末尾，出队操作将数组开头的元素移除。
2. 链表实现：使用链表来存储队列中的元素，同时使用两个指针分别指向链表的头部和尾部。入队操作将元素插入到链表的尾部，出队操作将链表头部的元素移除。

四、应用场景

队列在计算机科学和工程领域有着广泛的应用，例如：

1. 任务调度：操作系统中的进程调度和任务队列就是队列的典型应用场景，按照先进先出的原则进行任务调度。
2. 消息传递：在网络通信和消息队列中，队列用于存储和传递消息，确保消息按照先后顺序进行处理。
3. 缓冲区管理：队列可以用于实现缓冲区的管理，动态地添加和删除缓冲区中的数据。
4. 广度优先搜索：在图的广度优先搜索算法中，队列被用于保存当前节点的邻居节点，以便按照广度优先的顺序进行遍历。

五、实现

5.1 普通队列

/**
 * @Description 用链表实现队列
 * @Author lcy
 * @Date 2020/9/16 9:24
 */
public class LinkQueue<E> {

    public DoubleLinkedList<E> linkedList = new DoubleLinkedList<>();

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

    public boolean isEmpty(){
        return linkedList.size() == 0;
    }

    /**
     * 入队
     * @param element 元素
     * @author lcy
     * @date 2020/9/16 9:30
     **/
    public void enQueue(E element){
        linkedList.add(element);
    }

    /**
     * 出队
     * @return E
     * @author lcy
     * @date 2020/9/16 9:31
     **/
    public E deQueue(){
        return linkedList.remove(0);
    }

    /**
     * 获取队头
     * @return E
     * @author lcy
     * @date 2020/9/16 9:32
     **/
    public E feont(){
        return linkedList.get(0);
    }

    /**
     * 清空队列
     */
    public void clear(){
        linkedList.clear();
    }

    /**
     * 单向节点内部类
     * @author lcy
     * @date 2020/9/7 10:22
     **/
    static class Node<E> {

        /**
         * 当前节点值
         */
        E element;

        /**
         * 下个节点值
         */
        Node<E> next;

        public Node(E element,Node<E> next){
            this.element = element;
            this.next = next;

        }
    }

}

5.2 双向队列

/**
 * @Description 双端队列
 * @Author lcy
 * @Date 2020/9/18 9:34
 */
public class Deque<E> {

    public DoubleLinkedList<E> linkedList = new DoubleLinkedList<>();

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

    public boolean isEmpty(){
        return linkedList.size() == 0;
    }

    /**
     * 从队尾入队
     * @param element 元素
     * @author lcy
     * @date 2020/9/18 9:36
     **/
    public void enQueueRear(E element){
        linkedList.add(element);
    }

    /**
     * 从队尾出队
     * @return E
     * @author lcy
     * @date 2020/9/18 9:37
     **/
    public E deQueueRear(){
        return linkedList.remove(size() - 1);
    }

    /**
     * 获取队尾元素
     * @return E
     * @author lcy
     * @date 2020/9/18 9:37
     **/
    public E rear(){
        return linkedList.get(size() - 1);
    }

    /**
     * 从队头入队
     * @param element 元素
     * @author lcy
     * @date 2020/9/18 9:36
     **/
    public void enQueueFront(E element){
        linkedList.add(0,element);
    }

    /**
     * 从队头出队
     * @return E
     * @author lcy
     * @date 2020/9/18 9:37
     **/
    public E deQueueFront(){
        return linkedList.remove(0);
    }

    /**
     * 获取队头元素
     * @return E
     * @author lcy
     * @date 2020/9/18 9:37
     **/
    public E front(){
        return linkedList.get(0);
    }

    @Override public String toString(){
        return "Deque{" +
                "linkedList=" + linkedList +
                '}';
    }

    public static void main(String[] args){

        Deque<Object> deque = new Deque<>();
        deque.enQueueFront(1);
        System.out.println(deque);
        deque.enQueueFront(2);
        deque.enQueueRear(3);
        System.out.println(deque);
        System.out.println(deque.front());
        System.out.println(deque.rear());
        System.out.println(deque.deQueueFront());
        System.out.println(deque.deQueueRear());
        System.out.println(deque);

    }

}

六、总结

队列是一种常见的数据结构，具有先进先出的特性，适用于各种需要按照顺序存储和处理数据的场景。队列可以通过数组或链表等不同的数据结构来实现，每种实现方式都有着各自的特点和适用范围。对队列的深入理解和熟练运用，有助于提高程序的效率和性能。