[数据结构与算法]手写Queue(顺序映像、非顺序映像)，及其应用场景

1 队列的顺序映像

import com.cskaoyan.exception.EmptyQueueException;

/**
 * 顺序映像(底层是循环数组)实现队列，可扩容
 * @author PorscheYe
 * @version v1.0
 */

/*
有的教材上应用循环队列实现顺序映像结构的队列时，对于判断队空和队满：
    队空：front == rear
    队满：front == (rear + 1) % elements.length
其中front指向队头元素的前一个位置，rear指向队尾元素；或者front指向队头元素，rear指向队尾元素的后一个位置。
但是这需要浪费数组的一个空间，如果不想浪费数组的一个空间，可以再设置一个属性size，
当 size == 0 时，队空；当 size == elements.length 时，队满。此时front指向队头元素，rear指向队尾元素。
 */

public class MyQueue {
    // 属性
    private static final int MAX_CAPACITY = Integer.MAX_VALUE - 8;
    private static final int DEFAULT_CAPACITY = 10;

    private int front; // 队头元素索引值
    private int rear; // 队尾元素索引值
    private int size; // 元素的个数，用于判断队空和队满
    private String[] elements; // 底层存放数据的容器

    // 构造函数
    public MyQueue() {
        elements = new String[DEFAULT_CAPACITY];
        front = 0;
        rear = elements.length - 1;
    }

    public MyQueue(int capacity) {
        if (capacity > MAX_CAPACITY || capacity < 0) {
            throw new IllegalArgumentException("capacity = " + capacity);
        }
        elements = new String[capacity];
        front = 0;
        rear = elements.length - 1;
    }

    /**
     * 指定元素入队列(可扩容)
     * @param s 指定元素
     */
    public void enque(String s) {
        if (size + 1 > elements.length) {
            // 需要进行扩容
            if (size + 1 > MAX_CAPACITY) {
                throw new ArrayStoreException(); // 容纳不下
            }
            // 一定能够容纳下
            int len = elements.length + (elements.length >> 1);
            if (len > MAX_CAPACITY || len < 0) {
                len = MAX_CAPACITY;
            }
            int newLength = len > (size + 1) ? len : size + 1;
            grow(newLength);
        }
        // 扩容结束
        rear = (rear + 1) % elements.length;
        elements[rear] = s;
        size++;
    }

    private void grow(int newLength) {
        String[] arr = new String[newLength];
        for (int i = 0; i < size; i++) {
            arr[i] = elements[(front + i) % elements.length];
        }
        elements = arr;
        front = 0;
        rear = size - 1;
    }

    /**
     * 队头元素出队列
     * @return 返回队头元素
     */
    public String deque() {
        if (isEmpty()) {
            throw new EmptyQueueException();
        }
        String retVal = elements[front];
        front = (front + 1) % elements.length;
        size--;
        return retVal;
    }

    /**
     * 查看栈顶元素的值
     * @return 栈顶元素的值
     */
    public String peek() {
        if (isEmpty()) {
            throw new EmptyQueueException();
        }
        return elements[front];
    }

    /**
     * 判空
     * @return 如果为空返回true，否则返回false
     */
    public boolean isEmpty() {
        return size == 0;
    }
}

自定义的EmptyQueueException：

/*
自定义异常：
    必须要继承 Exception 和 RuntimeException
    继承 Exception, 强制性处理，需要try... catch或上抛
    继承 RuntimeException, 选择性处理，可以不用try... catch和上抛
 */

public class EmptyQueueException extends RuntimeException {
    public EmptyQueueException() {
        super();
    }

    public EmptyQueueException(String message) {
        super(message);
    }
}

2 队列的应用场景

1. 普通队列应用场景十分有限。
2. 阻塞队列：
   enque(): 当队列满时，阻塞，等待队列不满时，再入队列，并返回。
   deque(): 当队列空时，阻塞，等待队列不空时，再出队列，并返回。
3. 并发队列
   线程安全的队列
4. 缓存
5. 广度优先遍历

结束语：如果本篇博客对您有帮助，请点赞、收藏或关注，您的鼓励是博主进步的动力，感谢支持，共同进步。