面试算法大全-队列总结

布满荆棘的人生 2022-10-17 13:50 176阅读 0赞

### 5.1 队列的定义和特点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1OTY0NTU_size_16_color_FFFFFF_t_70_pic_center]

### 5.2 队列的实现 ###

#### 5.2.1 用数组实现队列 ####

// 使用数组模拟队列-编写一个ArrayQueue类
    class ArrayQueue {
        
    	private int maxSize; // 表示数组的最大容量
    	private int front; // 队列头
    	private int rear; // 队列尾
    	private int[] arr; // 该数据用于存放数据, 模拟队列
    	// 创建队列的构造器
    	public ArrayQueue(int arrMaxSize) {
        
    		maxSize = arrMaxSize;
    		arr = new int[maxSize];
    		front = -1; // 指向队列头部，分析出front是指向队列头的前一个位置.
    		rear = -1; // 指向队列尾，指向队列尾的数据(即就是队列最后一个数据)
    	}
    	// 判断队列是否满
    	public boolean isFull() {
        
    		return rear == maxSize - 1;
    	}
    	// 判断队列是否为空
    	public boolean isEmpty() {
        
    		return rear == front;
    	}
    
    	// 添加数据到队列
    	public void addQueue(int n) {
        
    		// 判断队列是否满
    		if (isFull()) {
        
    			System.out.println("队列满，不能加入数据~");
    			return;
    		}
    		rear++; // 让rear 后移
    		arr[rear] = n;
    	}
    	// 获取队列的数据, 出队列
    	public int getQueue() {
        
    		// 判断队列是否空
    		if (isEmpty()) {
        
    			// 通过抛出异常
    			throw new RuntimeException("队列空，不能取数据");
    		}
    		front++; // front后移
    		return arr[front];
    
    	}
    	// 显示队列的所有数据
    	public void showQueue() {
        
    		// 遍历
    		if (isEmpty()) {
        
    			System.out.println("队列空的，没有数据~~");
    			return;
    		}
    		for (int i = 0; i < arr.length; i++) {
        
    			System.out.printf("arr[%d]=%d\n", i, arr[i]);
    		}
    	}
    	// 显示队列的头数据， 注意不是取出数据
    	public int headQueue() {
        
    		// 判断
    		if (isEmpty()) {
        
    			throw new RuntimeException("队列空的，没有数据~~");
    		}
    		return arr[front + 1];
    	}
    }

#### 5.2.2 用链表实现队列 ####

public interface Queue<E> {
        
        int getSize();
        boolean isEmpty();
        void enqueue(E e);
        E dequeue();
        E getFront();
    }
    
    public class LinklistQueue<E> implements Queue<E>{
        
        /*
        内部类
         */
        private class Node<E>{
        
            E e;
            Node<E> next;
            public Node(E e,Node next){
        
                this.e=e;
                this.next=next;
            }
            public Node(E e){
        
                this(e,null);
            }
            public Node(){
        
                this(null,null);
            }
        }
        private Node head,tail;
        private int size;
        /*
        构造函数
         */
        public LinklistQueue(){
        
            head=tail=null;
            size=0;
        }
        /*
        功能实现
         */
        @Override
        public boolean isEmpty(){
        
            return (size==0);
        }
    
        @Override
        public int getSize(){
        
            return size;
        }
    
        @Override
        public void enqueue(E e){
        
            if(size==0){
        
                tail=head=new Node(e);
            }//特殊情况，入队前队列为空 head和tail都为null
            else{
        
                tail.next=new Node(e);
                tail=tail.next;
            }
            size++;
        }
    
        @Override
        public E dequeue(){
        
            if(size==0){
        
                throw new IllegalArgumentException("无法从空队列中出队");
            }
            Node ret=head;
            head=head.next;
            ret.next=null;
            if(head==null){
        
                tail=null;
            }//特殊情况：出队后队列变空
            size--;
            return (E)ret.e;
        }
    
        @Override
        public E getFront(){
        
            return (E)head.e;
        }
    }

#### 5.2.3用两个栈实现队列 ####

import java.util.Stack;
     
    public class Solution {
        
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
         
        public void push(int node) {
        
            stack1.push(node);
        }
         
        public int pop() {
        
            if(stack2.empty())
            {
        
                while(stack1.empty() != true)
                {
        
                    stack2.push(stack1.pop());
                }
            }
            if(stack2.empty() == true)
            {
        
                return -1;
            }
            return stack2.pop();
        }
    }

#### 5.2.4 循环队列 ####

//循环队列
    class CirQueue {
        
        private int QueueSize;
        private int front;
        private int rear;
        private int[] queueList;
        public CirQueue(int QueueSize) {
        
            this.QueueSize = QueueSize;
            queueList = new int[QueueSize];
            front = 0;
            rear = 0;
        }
        //获取队列头元素
        public int getQueueElement() {
        
            //如果队列不为空，返回队头元素，否则抛出异常提示队列为空
            int element = -1;
            if (!isEmpty()) {
        
                element = queueList[front];
                return element;
            } else {
        
                System.out.println("队列为空");
                return -1;
            }
    
        }
        //出队
        public int deQueue() {
        
            int element = -1;
            if (!isEmpty()) {
        
                element = queueList[front];
                front = (front + 1) % QueueSize;
                return element;
            } else {
        
                System.out.println("队列为空");
                return -1;
            }
    
        }
        //入队
        public void enQueue(int element) {
        
            //如果队列未满，添加元素到队尾，否则提示队列已满
            if (!isFull()) {
        
                queueList[rear] = element;
                rear = (rear + 1) % QueueSize;
    
            } else {
        
                System.out.println("队列已满");
            }
        }
        //判断队列是否为空
        public boolean isEmpty() {
        
            boolean b = false;
            if (rear == front) {
        
                b = true;
            }
            return b;
        }
        //判断队列是否已满
        public boolean isFull() {
        
            boolean b = false;
            if ((rear + 1) % QueueSize == front) {
        
                b = true;
            }
            return b;
        }
    
        public static void main(String[] args) {
        
            //新建并初始化存储空间为3的循环队列（方便判断队满条件，浪费一个数组空间）
            CirQueue cirQueue = new CirQueue(4);
            //入队3个元素
            cirQueue.enQueue(1);
            cirQueue.enQueue(2);
            cirQueue.enQueue(3);
            //获取队头元素,获取 但不改变队列
            int temp = cirQueue.getQueueElement();
            System.out.println(temp);
            //出队 获取队头元素，并且队头指针往后移一位
            temp = cirQueue.deQueue();
            System.out.println(temp);
            //再次获取队头元素
            temp = cirQueue.getQueueElement();
            System.out.println(temp);
        }
    }

第二种实现形式

class CircleArray {
        
        private int maxSize; // 表示数组的最大容量
        //front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
        //front 的初始值 = 0
        private int front;
        //rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
        //rear 的初始值 = 0
        private int rear; // 队列尾
        private int[] arr; // 该数据用于存放数据, 模拟队列
    
        public CircleArray(int arrMaxSize) {
        
            maxSize = arrMaxSize;
            arr = new int[maxSize];
        }
        // 判断队列是否满
        public boolean isFull() {
        
            return (rear  + 1) % maxSize == front;
        }
        // 判断队列是否为空
        public boolean isEmpty() {
        
            return rear == front;
        }
        // 添加数据到队列
        public void addQueue(int n) {
        
            // 判断队列是否满
            if (isFull()) {
        
                System.out.println("队列满，不能加入数据~");
                return;
            }
            //直接将数据加入
            arr[rear] = n;
            //将 rear 后移, 这里必须考虑取模
            rear = (rear + 1) % maxSize;
        }
        // 获取队列的数据, 出队列
        public int getQueue() {
        
            // 判断队列是否空
            if (isEmpty()) {
        
                // 通过抛出异常
                throw new RuntimeException("队列空，不能取数据");
            }
            // 这里需要分析出 front是指向队列的第一个元素
            // 1. 先把 front 对应的值保留到一个临时变量
            // 2. 将 front 后移, 考虑取模
            // 3. 将临时保存的变量返回
            int value = arr[front];
            front = (front + 1) % maxSize;
            return value;
    
        }
        // 显示队列的所有数据
        public void showQueue() {
        
            // 遍历
            if (isEmpty()) {
        
                System.out.println("队列空的，没有数据~~");
                return;
            }
            // 思路：从front开始遍历，遍历多少个元素
            // 动脑筋
            for (int i = front; i < front + size() ; i++) {
        
                System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
            }
        }
        // 求出当前队列有效数据的个数
        public int size() {
        
            // rear = 2
            // front = 1
            // maxSize = 3
            return (rear + maxSize - front) % maxSize;
        }
        // 显示队列的头数据， 注意不是取出数据
        public int headQueue() {
        
            // 判断
            if (isEmpty()) {
        
                throw new RuntimeException("队列空的，没有数据~~");
            }
            return arr[front];
        }
    }

#### 5.2.5 双端队列(基于数组) ####

/**
     * 双端队列 ADT接口
     * */
    public interface Deque<E>{
        
        /**
         * 头部元素插入
         * */
        void addHead(E e);
        /**
         * 尾部元素插入
         * */
        void addTail(E e);
        /**
         * 头部元素删除
         * */
        E removeHead();
        /**
         * 尾部元素删除
         * */
        E removeTail();
        /**
         * 窥视头部元素(不删除)
         * */
        E peekHead();
        /**
         * 窥视尾部元素(不删除)
         * */
        E peekTail();
        /**
         * @return 返回当前队列中元素的个数
         */
        int size();
        /**
         * 判断当前队列是否为空
         * @return 如果当前队列中元素个数为0，返回true；否则，返回false
         */
        boolean isEmpty();
        /**
         * 清除队列中所有元素
         * */
        void clear();
        /**
         * 获得迭代器
         * */
        Iterator<E> iterator();
    }

/**
     * 基于数组的 双端队列
     * */
    public class ArrayDeque<E> implements Deque<E>{
        
        //===============================================成员变量======================================================
        /**
         * 内部封装的数组
         * */
        private Object[] elements;
        /**
         * 队列默认的容量大小
         * */
        private static final int DEFAULT_CAPACITY = 16;
        /**
         * 扩容翻倍的基数
         * */
        private static final int EXPAND_BASE = 2;
        /**
         * 队列头部下标
         * */
        private int head;
        /**
         * 队列尾部下标
         * */
        private int tail;
        //=================================================构造方法======================================================
        /**
         * 默认构造方法
         * */
        public ArrayDeque() {
        
            // 设置数组大小为默认
            this.elements = new Object[DEFAULT_CAPACITY];
    
            // 初始化队列 头部,尾部下标
            this.head = 0;
            this.tail = 0;
        }
        /**
         * 默认构造方法
         * */
        public ArrayDeque(int initCapacity) {
        
            assert initCapacity > 0;
            // 设置数组大小为默认
            this.elements = new Object[initCapacity];
            // 初始化队列 头部,尾部下标
            this.head = 0;
            this.tail = 0;
        }
        //===============================================内部辅助方法===================================================
        /**
         * 快速取模
         * */
        private int getMod(int logicIndex){
        
            int innerArrayLength = this.elements.length;
            // 由于队列下标逻辑上是循环的
            if(logicIndex < 0){
        
                // 当逻辑下标小于零时
                // 加上当前数组长度
                logicIndex += innerArrayLength;
            } else if(logicIndex >= innerArrayLength){
        
                // 当逻辑下标大于数组长度时
                // 减去当前数组长度
                logicIndex -= innerArrayLength;
            }
            // 获得真实下标
            return logicIndex;
        }
        /**
         * 内部数组扩容
         * */
        private void expand(){
        
            // 内部数组 扩容两倍
            int elementsLength = this.elements.length;
            Object[] newElements = new Object[elementsLength * EXPAND_BASE];
            // 将"head -> 数组尾部"的元素 复制在新数组的前面 使用System.arraycopy效率更高
            for(int i=this.head, j=0; i<elementsLength; i++,j++){
        
                newElements[j] = this.elements[i];
            }
            // 将"0 -> head"的元素 复制在新数组的后面 使用System.arraycopy效率更高
            for(int i=0, j=elementsLength-this.head; i<this.head; i++,j++){
        
                newElements[j] = this.elements[i];
            }
            // 初始化head,tail下标
            this.head = 0;
            this.tail = this.elements.length;
            // 内部数组指向 新扩容的数组
            this.elements = newElements;
        }
        //=================================================外部接口=======================================================
        @Override
        public void addHead(E e) {
        
            // 头部插入元素 head下标前移一位
            this.head = getMod(this.head - 1);
            // 存放新插入的元素
            this.elements[this.head] = e;
            // 判断当前队列大小 是否到达临界点
            if(head == tail){
        
                // 内部数组扩容
                expand();
            }
        }
        @Override
        public void addTail(E e) {
        
            // 存放新插入的元素
            this.elements[this.tail] = e;
            // 尾部插入元素 tail下标后移一位
            this.tail = getMod(this.tail + 1);
            // 判断当前队列大小 是否到达临界点
            if(head == tail){
        
                // 内部数组扩容
                expand();
            }
        }
        @Override
        @SuppressWarnings("unchecked")
        public E removeHead() {
        
            // 暂存需要被删除的数据
            E dataNeedRemove = (E)this.elements[this.head];
            // 将当前头部元素引用释放
            this.elements[this.head] = null;
            // 头部下标 后移一位
            this.head = getMod(this.head + 1);
            return dataNeedRemove;
        }
        @Override
        @SuppressWarnings("unchecked")
        public E removeTail() {
        
            // 获得尾部元素下标(前移一位)
            int lastIndex = getMod(this.tail - 1);
            // 暂存需要被删除的数据
            E dataNeedRemove = (E)this.elements[lastIndex];
            // 设置尾部下标
            this.tail = lastIndex;
            return dataNeedRemove;
        }
        @Override
        @SuppressWarnings("unchecked")
        public E peekHead() {
        
            return (E)this.elements[this.head];
        }
        @Override
        @SuppressWarnings("unchecked")
        public E peekTail() {
        
            // 获得尾部元素下标(前移一位)
            int lastIndex = getMod(this.tail - 1);
            return (E)this.elements[lastIndex];
        }
    
        @Override
        public int size() {
        
            return getMod(tail - head);
        }
        @Override
        public boolean isEmpty() {
        
            // 当且仅当 头尾下标相等时 队列为空
            return (head == tail);
        }
        @Override
        public void clear() {
        
            int head = this.head;
            int tail = this.tail;
            while(head != tail){
        
                this.elements[head] = null;
                head = getMod(head + 1);
            }
            this.head = 0;
            this.tail = 0;
        }
        @Override
        public Iterator<E> iterator() {
        
            return new Itr();
        }
        @Override
        public String toString() {
        
            Iterator<E> iterator = this.iterator();
            // 空列表
            if(!iterator.hasNext()){
        
                return "[]";
            }
            // 列表起始使用"["
            StringBuilder s = new StringBuilder("[");
            // 反复迭代
            while(true){
        
                // 获得迭代的当前元素
                E data = iterator.next();
                // 判断当前元素是否是最后一个元素
                if(!iterator.hasNext()){
        
                    // 是最后一个元素，用"]"收尾
                    s.append(data).append("]");
                    // 返回 拼接完毕的字符串
                    return s.toString();
                }else{
        
                    // 不是最后一个元素
                    // 使用", "分割，拼接到后面
                    s.append(data).append(", ");
                }
            }
        }
        /**
         * 双向队列 迭代器实现
         * */
        private class Itr implements Iterator<E> {
        
            /**
             * 当前迭代下标 = head
             * 代表遍历从头部开始
             * */
            private int currentIndex = ArrayDeque.this.head;
            /**
             * 目标终点下标 = tail
             * 代表遍历至尾部结束
             * */
            private int targetIndex = ArrayDeque.this.tail;
            /**
             * 上一次返回的位置下标
             * */
            private int lastReturned;
            @Override
            public boolean hasNext() {
        
                // 当前迭代下标未到达终点，还存在下一个元素
                return this.currentIndex != this.targetIndex;
            }
            @Override
            @SuppressWarnings("unchecked")
            public E next() {
        
                // 先暂存需要返回的元素
                E value = (E)ArrayDeque.this.elements[this.currentIndex];
                // 最近一次返回元素下标 = 当前迭代下标
                this.lastReturned = this.currentIndex;
                // 当前迭代下标 向后移动一位(需要取模)
                this.currentIndex = getMod(this.currentIndex + 1);
                return value;
            }
            @Override
            public void remove() {
        
                if(this.lastReturned == -1){
        
                    throw new IteratorStateErrorException("迭代器状态异常: 可能在一次迭代中进行了多次remove操作");
                }
                // 删除当前迭代下标的元素
                boolean deleteFromTail = delete(this.currentIndex);
                // 如果从尾部进行收缩
                if(deleteFromTail){
        
                    // 当前迭代下标前移一位
                    this.currentIndex = getMod(this.currentIndex - 1);
                }
                // 为了防止用户在一次迭代(next调用)中多次使用remove方法，将lastReturned设置为-1
                this.lastReturned = -1;
            }
            /**
             * 删除队列内部数组特定下标处的元素
             * @param currentIndex 指定的下标
             * @return true 被删除的元素靠近尾部
             *          false 被删除的元素靠近头部
             * */
            private boolean delete(int currentIndex){
        
                Object[] elements = ArrayDeque.this.elements;
                int head = ArrayDeque.this.head;
                int tail = ArrayDeque.this.tail;
                // 当前下标 之前的元素个数
                int beforeCount = getMod(currentIndex - head);
                // 当前下标 之后的元素个数
                int afterCount = getMod(tail - currentIndex);
                // 判断哪一端的元素个数较少
                if(beforeCount < afterCount){
        
                    // 距离头部元素较少，整体移动前半段元素
                    // 判断头部下标 是否小于 当前下标
                    if(head < currentIndex){
        
                        // 小于，正常状态  仅需要复制一批数据
                        // 将当前数组从"头部下标"开始，整体向右平移一位，移动的元素个数为"当前下标 之前的元素个数"
                        System.arraycopy(elements,head,elements,head+1,beforeCount);
                    }else{
        
                        // 不小于，说明存在溢出环  需要复制两批数据
                        // 将数组从"0下标处"的元素整体向右平移一位，移动的元素个数为"从0到当前下标之间的元素个数"
                        System.arraycopy(elements,0,elements,1,currentIndex);
                        // 将数组最尾部的数据设置到头部，防止被覆盖
                        elements[0] = elements[(elements.length-1)];
                        // 将数组尾部的数据整体向右平移一位
                        System.arraycopy(elements,head,elements,head+1,(elements.length-head-1));
                    }
                    // 释放被删除元素的引用
                    elements[currentIndex] = null;
                    // 头部下标 向右移动一位
                    ArrayDeque.this.head = getMod(ArrayDeque.this.head + 1);
                    // 没有删除尾部元素 返回false
                    return false;
                }else{
        
                    // 距离尾部元素较少，整体移动后半段元素
                    // 判断尾部下标 是否小于 当前下标
                    if(currentIndex < tail){
        
                        // 小于，正常状态  仅需要复制一批数据
                        // 将当前数组从"当前"开始，整体向左平移一位，移动的元素个数为"当前下标 之后的元素个数"
                        System.arraycopy(elements,currentIndex+1,elements,currentIndex,afterCount);
                    }else{
        
                        // 不小于，说明存在溢出环  需要复制两批数据
                        // 将数组从"当前下标处"的元素整体向左平移一位，移动的元素个数为"从当前下标到数组末尾的元素个数-1 ps：因为要去除掉被删除的元素"
                        System.arraycopy(elements,currentIndex+1,elements,currentIndex,(elements.length-currentIndex-1));
                        // 将数组头部的元素设置到末尾
                        elements[elements.length-1] = elements[0];
                        // 将数组头部的数据整体向左平移一位，移动的元素个数为"从0到尾部下标之间的元素个数"
                        System.arraycopy(elements,1,elements,0,tail);
                    }
                    // 尾部下标 向左移动一位
                    ArrayDeque.this.tail = getMod(ArrayDeque.this.tail - 1);
    
                    // 删除了尾部元素 返回true
                    return true;
                }
            }
        }
    }

### 5.3 经典题目源码 ###

#### [滑动窗口的最大值][Link 1] ####

class Solution1 {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
        
            if(nums.length == 0 || k == 0) {
        
                return new int[0];
            }
            Deque<Integer> deque = new LinkedList<>();
            int[] res = new int[nums.length - k + 1];
            for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
        
                if(i > 0 && deque.peekFirst() == nums[i - 1]) {
        
                    deque.removeFirst(); // 删除 deque 中对应的 nums[i-1]
                }
                while(!deque.isEmpty() && deque.peekLast() < nums[j]) {
        
                    deque.removeLast(); // 保持 deque 递减
                }
                deque.addLast(nums[j]);
                if(i >= 0) {
        
                    res[i] = deque.peekFirst();  // 记录窗口最大值
                }
            }
            return res;
        }
    }

class Solution {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
        
            if(nums.length == 0 || k == 0) return new int[0];
            Deque<Integer> deque = new LinkedList<>();
            int[] res = new int[nums.length - k + 1];
            for(int i = 0; i < k; i++) {
         // 未形成窗口
                while(!deque.isEmpty() && deque.peekLast() < nums[i])
                    deque.removeLast();
                deque.addLast(nums[i]);
            }
            res[0] = deque.peekFirst();
            for(int i = k; i < nums.length; i++) {
         // 形成窗口后
                if(deque.peekFirst() == nums[i - k])
                    deque.removeFirst();
                while(!deque.isEmpty() && deque.peekLast() < nums[i])
                    deque.removeLast();
                deque.addLast(nums[i]);
                res[i - k + 1] = deque.peekFirst();
            }
            return res;
        }
    }

#### [设计循环双端队列][Link 2] ####

public class MyCircularDeque {
        
    
        // 1、不用设计成动态数组，使用静态数组即可
        // 2、设计 head 和 tail 指针变量
        // 3、head == tail 成立的时候表示队列为空
        // 4、tail + 1 == head
        private int capacity;
        private int[] arr;
        private int front;
        private int rear;
        /**
         * Initialize your data structure here. Set the size of the deque to be k.
         */
        public MyCircularDeque(int k) {
        
            capacity = k + 1;
            arr = new int[capacity];
            // 头部指向第 1 个存放元素的位置
            // 插入时，先减，再赋值
            // 删除时，索引 +1（注意取模）
            front = 0;
            // 尾部指向下一个插入元素的位置
            // 插入时，先赋值，再加
            // 删除时，索引 -1（注意取模）
            rear = 0;
        }
        /**
         * Adds an item at the front of Deque. Return true if the operation is successful.
         */
        public boolean insertFront(int value) {
        
            if (isFull()) {
        
                return false;
            }
            front = (front - 1 + capacity) % capacity;
            arr[front] = value;
            return true;
        }
        /**
         * Adds an item at the rear of Deque. Return true if the operation is successful.
         */
        public boolean insertLast(int value) {
        
            if (isFull()) {
        
                return false;
            }
            arr[rear] = value;
            rear = (rear + 1) % capacity;
            return true;
        }
        /**
         * Deletes an item from the front of Deque. Return true if the operation is successful.
         */
        public boolean deleteFront() {
        
            if (isEmpty()) {
        
                return false;
            }
            // front 被设计在数组的开头，所以是 +1
            front = (front + 1) % capacity;
            return true;
        }
        /**
         * Deletes an item from the rear of Deque. Return true if the operation is successful.
         */
        public boolean deleteLast() {
        
            if (isEmpty()) {
        
                return false;
            }
            // rear 被设计在数组的末尾，所以是 -1
            rear = (rear - 1 + capacity) % capacity;
            return true;
        }
        /**
         * Get the front item from the deque.
         */
        public int getFront() {
        
            if (isEmpty()) {
        
                return -1;
            }
            return arr[front];
        }
        /**
         * Get the last item from the deque.
         */
        public int getRear() {
        
            if (isEmpty()) {
        
                return -1;
            }
            // 当 rear 为 0 时防止数组越界
            return arr[(rear - 1 + capacity) % capacity];
        }
        /**
         * Checks whether the circular deque is empty or not.
         */
        public boolean isEmpty() {
        
            return front == rear;
        }
        /**
         * Checks whether the circular deque is full or not.
         */
        public boolean isFull() {
        
            // 注意：这个设计是非常经典的做法
            return (rear + 1) % capacity == front;
        }
    }

#### 数据流中的移动平均值 ####

public class MovingAverage {
        
        private double previousSum = 0.0;
        private int maxSize;
        private Queue<Integer> currentWindow;
        /** Initialize your data structure here. */
        public MovingAverage(int size) {
        
            currentWindow = new LinkedList<Integer>();
            maxSize = size;
        }
         
        public double next(int val) {
        
            if(currentWindow.size()==maxSize){
        
                previousSum -= currentWindow.remove();
            }
            currentWindow.add(val);
            previousSum += val;
            return previousSum/currentWindow.size();
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1OTY0NTU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/ae8be5e514e74ed880acc8ff62337e12.png
[Link 1]: https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
[Link 2]: https://leetcode-cn.com/problems/design-circular-deque/