1 队列介绍

1.1 定义

队列是一种特殊的线性表,遵循FIFO(first in first out)先进先出原则,整个队列由一个线性表构成,可以是数组或者链表,同时由队头(font)来表示第一个元素、队尾(rear)最后一个元素,并且队列只允许在队头删除元素,队尾添加元素

1.2 本例仓库地址

仓库地址:https://gitee.com/bean-chan/data-structure.git

2 三种队列

2.1 普通队列

2.1.1 实现原理

创建之初,队头与队尾处在第一个位置上

随后往队伍里连续先后添加两个元素A与B后

队尾向后连续位移两个位置,并且每添加一次元素,队尾就会向后位移一个位置,直到整个线性表最末端为止,此时则队列不再允许添加元素

我们进行删除操作时,队头会向后位移一个位置,例如我们将A出队

之后再将B出队

当队头与队尾指向同一位置时,说明此刻队列为空

2.1.2 基于数组实现

import java.util.Arrays;

/**
 * @Classname NormalQueue
 * @Author ChenBin
 * @Description
 * @CreateDate 2021/3/4 1:35 PM
 */
public class NormalQueue {
    private Integer[] dataArr; // 存放元素的数组
    private int capacity; // 容量
    private int font; // 队头指针
    private int rear; // 队尾指针
    private static final int DEFAULT_SIZE = 6; // 默认容量

    // 构造器
    public NormalQueue() {
        this.dataArr = new Integer[DEFAULT_SIZE];
        this.capacity = DEFAULT_SIZE;
        this.font = 0;
        this.rear = 0;
    }

    // 队列是否为空
    public boolean isEmpty() {
        return rear - font == 0;
    }

    // 查看队首元素
    public Integer peek() {
        if (isEmpty()) return null;
        return dataArr[rear - 1];
    }

    // 入队一个元素
    public void push(Integer val) {
        checkCapacity();
        dataArr[rear] = val;
        rear++;
    }

    // 出队一个元素
    public Integer pop() {
        if (isEmpty()) return null;
        checkCapacity();
        Integer temp = dataArr[font];
        dataArr[font++] = null;
        return temp;
    }

    // 容量检查
    private void checkCapacity() {
        if (rear >= capacity) {
            // 空间不足,扩容
            capacity = capacity * 2;
            Integer[] tempArr = new Integer[capacity];
            System.arraycopy(dataArr, 0, tempArr, 0, rear - font);
            this.dataArr = tempArr;
        }
    }

    public void print() {
        System.out.println(
                "NormalQueue{" +
                        "dataArr=" + Arrays.toString(dataArr) +
                        ", capacity=" + capacity +
                        ", font=" + font +
                        ", rear=" + rear +
                        '}'
        );
    }

    public static void main(String[] args) {
        NormalQueue queue = new NormalQueue();
        System.out.println(queue.peek());
        queue.print();
        queue.push(1);
        queue.push(2);
        queue.push(3);
        queue.push(4);
        queue.push(5);
        queue.push(6);
        queue.push(7);
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        queue.print();
    }
}

2.2 循环队列

2.2.1 实现原理

普通队列最大的缺点就是出队后空出来的位置无法复用,而循环队列很好的解决了这个问题

跟普通队列一样,一开始,队头队尾指向第一个位置

连续添加五个元素

此时,再添加一个元素时,队尾指针就会超出最大容量,此时队尾指针就成了空指针,而循环队列为了避免这种情况,采用对最大值取模的方式,让队尾指针重新指向队头

由普通队列得知,当队头与队尾指针指向同一位置时,内容为空,但此时内容满了发现队头与队尾也指向相同位置

此处解决方案有二:

1. 添加一个size属性代表元素容量,当队头与队尾指向同一元素时,如果size>0,则代表队满,如果size=0,则代表队空

2. 让队头的前一个位置为空置位,不得塞元素,如下图,此时最大容量为5,即元素F无法入队,当前队列已满,只有出队一个元素才可以再入队

   

基于方案二,此时再删除一个元素A、添加一个F,则此时队列情况如下

2.2.2 基于数组实现(方案二)

import java.util.Arrays;

/**
 * @Classname NormalQueue
 * @Author ChenBin
 * @Description
 * @CreateDate 2021/3/4 1:35 PM
 */
public class CircularQueue {
    private Integer[] dataArr;
    private int capacity;
    private int font;
    private int rear;
    private static final int DEFAULT_SIZE = 6;

    // 构造器
    public CircularQueue() {
        this.dataArr = new Integer[DEFAULT_SIZE];
        this.capacity = DEFAULT_SIZE;
        this.font = 0;
        this.rear = 0;
    }

    // 队列是否为空
    public boolean isEmpty() {
        return rear - font == 0;
    }

    // 查看队首元素
    public Integer peek() {
        if (isEmpty()) return null;
        // rear先加capacity,再对capacity取模
        return dataArr[(rear + capacity - 1) % capacity];
    }

    // 入队一个元素
    public void push(Integer val) {
        // 队满
        if ((rear + 1) % capacity == font) {
            System.out.println("队满,无法添加");
            return;
        }
        dataArr[(rear) % capacity] = val;
        rear = (rear + 1) % capacity;
    }

    // 出队一个元素
    public Integer pop() {
        if (isEmpty()) return null;
        Integer temp = dataArr[(font + capacity) % capacity];
        dataArr[(font + capacity) % capacity] = null;
        font++;
        return temp;
    }


    public void print() {
        System.out.println(
                "NormalQueue{" +
                        "dataArr=" + Arrays.toString(dataArr) +
                        ", capacity=" + capacity +
                        ", font=" + font +
                        ", rear=" + rear +
                        '}'
        );
    }

    public static void main(String[] args) {
        CircularQueue queue = new CircularQueue();
//        System.out.println(queue.peek());
        queue.print();
        queue.push(1);
        queue.print();
        queue.push(2);
        queue.push(3);
        queue.push(4);
        queue.push(5);
        queue.print();
        queue.push(6);
        queue.print();
        System.out.println(queue.pop());
        queue.print();
        System.out.println(queue.pop());
        queue.print();
        System.out.println(queue.pop());
        queue.print();
        System.out.println(queue.pop());
        queue.print();
        System.out.println(queue.pop());
        queue.print();
        System.out.println(queue.pop());
        queue.push(6);
        queue.push(7);
        queue.print();
    }
}

2.3 双端队列

2.3.1 实现原理

前两种队列都只能做到队头出,队尾进,尽管这也是队列设计出来的初衷,但是有些情况就是需要既可以队头进出元素,又可以队尾进出元素,而这就是双端队列

具体原理与普通队列相似,只是首尾都可以进出元素,除了有后继指针外,还需要前驱指针,否则队尾弹出元素后无法指定队尾

2.3.2 基于链表实现

/**
 * @Classname Node
 * @Author ChenBin
 * @Description
 * @CreateDate 2021/3/4 4:27 PM
 */
class Node {
    // 节点值
    Integer value;
    // 后继
    Node next;
    // 前驱
    Node prev;

    public Node() {
    }

    public Node(Integer value) {
        this.value = value;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

import java.util.Arrays;

/**
 * @Classname NormalQueue
 * @Author ChenBin
 * @Description
 * @CreateDate 2021/3/4 1:35 PM
 */
public class Deque {
  
    // 队头
    Node head;
    // 队尾
    Node rear;
    int size;

    public Deque() {
        head = new Node();
        rear = head;
        size = 0;
    }

    // 队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 查看队首元素
    public Integer peek() {
        if (isEmpty()) return null;
        return head.next.value;
    }

    // 队头入队一个元素
    public void addFirst(Integer val) {
        size++;
        Node node = new Node(val);
        node.next = head.next;
        if (head.next != null)
            head.next.prev = node;
        head.next = node;
        node.prev = head;
        if (size == 1) {
            rear = node;
        }

    }

    // 队尾入队一个元素
    public void addLast(Integer val) {
        size++;
        Node newNode = new Node(val);
        newNode.prev = rear;
        rear.next = newNode;
        rear = newNode;
    }

    // 队头出队一个元素
    public Integer removeFirst() {

        if (size == 0) return null;
        if (size == 1) {
            Integer val = head.next.value;
            head.next = null;
            rear = head;
            return val;
        }
        size = size - 1 < 0 ? 0 : size - 1;
        // 两个元素以上
        Node temp = head.next;
        temp.next.prev = head;
        head.next = temp.next;
        return temp.value;
    }

    // 队尾出队一个元素
    public Integer removeLast() {
        if (size == 0) return null;
        size = size - 1 < 0 ? 0 : size - 1;
        Node temp = rear.prev;
        rear = temp;
        rear.next = null;
        return temp.value;

    }

    public void print() {
        Node temp = head;
        System.out.print("Arr[ ");
        while (temp.next != null) {
            System.out.print(temp.next.value + " ");
            temp = temp.next;
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        Deque queue = new Deque();
        System.out.println(queue.peek());
        queue.addFirst(1);
        queue.print();
        queue.addLast(2);
        queue.addFirst(0);
        queue.print();
        queue.removeFirst();
        queue.print();
        queue.removeLast();
        queue.print();
        queue.removeFirst();
        queue.print();
    }
}