队列(Queue）的详解

     队列：只允许在一端进行插入操作，在另一端进行删除数据操作的特殊的线性表，队列具有先进先出

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

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

2、队列的使用

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

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

以下代码为Queue的代码演示

import java.util.LinkedList;
import java.util.Queue;
//Queue 的演示示例
public class Demo2 {
    public static void main(String[] args) {
        Queue queue = new LinkedList<>();
 
        System.out.println(queue.size());
        System.out.println(queue);
 
        System.out.println("===============================");
        //出队
        queue.poll();
        System.out.println(queue.peek());
        System.out.println(queue);
        System.out.println("===============================");
//        //删除，没有元素的时候会抛出异常
//        System.out.println(queue.remove());
//        System.out.println(queue);
//        System.out.println(queue);
//        //获取，没有元素的时候会抛出异常
//        System.out.println(queue.element());
//        System.out.println(queue);
    }
    public static void main1(String[] args) {
        Queue queue = new LinkedList<>();
        //入队
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        System.out.println(queue.size());
        System.out.println(queue);
 
        System.out.println("===============================");
        //出队
        queue.poll();
        System.out.println(queue.peek());
        System.out.println(queue);
        System.out.println("===============================");
        //删除
        System.out.println(queue.remove());
        System.out.println(queue);
        System.out.println(queue.remove(5));
        System.out.println(queue);
        //获取
        System.out.println(queue.element());
        System.out.println(queue);
    }
}

3、队列的模拟实现

//用双向链表实现
public class MyQueue {
 
    private static class ListNode {
        int val;
        ListNode prev;
        ListNode next;
 
        public ListNode(int val) {
            this.val = val;
        }
    }
    private ListNode head;
    private ListNode tail;
    public int size;
    public void offer (int e){
        ListNode node = new ListNode(e);
        if(head == null) {
            head = node;
        } else {
            tail.next = node;
            node.prev = tail;
        }
        tail = node;
        size++;
    }
 
    public int poll (){
        if(isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int headValue = head.val;
        head = head.next;
        if(head == null) {
            tail = null;
        } else {
            head.prev.next = null;
            head.prev = null;
        }
        size--;
        return headValue;
    }
 
    public int peek(){
        if(isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return head.val;
    }
    public int size (){
        return -1;
    }
 
    public boolean isEmpty() {
        return size == 0;
    }
 
    public void display(){
        ListNode cur = head;
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while(cur != null){
            sb.append(cur.val);
            if(cur.next != null){
                sb.append(",");
            }
            cur = cur.next;
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

 4、循环队列

       环形队列通常使用数组实现

注意：

      底层还是一个数组，指定一个队列的大小，入队时，当队列满的时候就不能再放了，出队时当队列为空的时候就不能再出队了 

      加一个冗余位置，当rear = front + 1这时，可以判定队列已满

      改变下标位置：（index + x）% array.length = 正确的下标

以下代码设计循环队列

class MyCircularQueue {
 
    private int[] elementData;
    private int front;
    private int rear;
    public MyCircularQueue(int k) {
        this.elementData = new int[k + 1];
    }
 
    //入队
    public boolean enQueue(int value) {
        if(isFull()) {
            return false;
        }
        elementData[rear] = value;
        rear = (rear + 1) % elementData.length;
        return true;
    }
 
    //出队
    public boolean deQueue() {
        if(isEmpty()) {
            return false;
        }
//        int res = elementData[front];出队的值
        front = (front + 1) % elementData.length;
        return true;
    }
 
    //取队首元素
    public int Front() {
        if(isEmpty()) {
            return -1;//在oj题不要抛异常，return-1即可
        }
        return elementData[front];
    }
 
    //取队尾元素
    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        return elementData[(rear - 1 + elementData.length) % elementData.length];
 
    }
    
    public boolean isEmpty() {
        return rear == front;
    }
 
    //判断是否已满
    public boolean isFull() {
        return (rear + 1) % elementData.length == front;
    }
}

5、双端队列（Deque）

     双端队列是指允许两端都可以进行入队和出队的操作的队列，Deque是一个接口，使用时必须创建LinkedList的对象

注意：栈，在Java中是用数组实现的，Stack继承自Vector，性质是后进先出 LIFO

          队列，在Java中是用双向链表实现的，实现类是LinkedList，性质是先进先出 FIFO