自己写一个环形队列(java实现)

àì夳堔傛蜴生んèń 2022-12-10 14:53 154阅读 0赞

环形队列的实现其实挺简单 但有些关键的因素要记住

先看图

下面是 初始化状态的 定义两个指针 默认都为0  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]

这队列满了的情况 rear指针会指向最后元素+1的位置

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

重点来了 如果知道队列为空呢

是不是 两个指针同时指向一个位置的时候？

也就是

**front==rear**

队列为满的条件呢

**(rear + 1) % maxsize == front**

maxsize指的就是数组长度了

其实这是个公式 代换进去 验证一下就可以了

可以这么记 指向尾部的指针+1 就与头指针重叠了 再取模运算 判断队列满

还有求队列有效元素的公式

**(rear - front+ maxsize) % maxsize**

尾指针-头指针可能为负 需要加上队列长度 再取模就出来有效元素个数了

还有入队出队的操作 记住一点 入队动rear 出队动front就能搞定了

下面是代码

/** * 以数组为底层的双端队列 */
    class MyCircleQueue { 
        /** * front默认指向第一个元素 默认为0 * rear指向最后一个元素的后一个位置 默认为0 * max 定义环形队列的大小 但默认会空出一个位置来判断队列是否满 * 所以真实存放的数据为数组长度-1 */
        int front;
        int rear;
        int maxsize;
        int[] data;
    
        /** * @param maxsize 构造函数初始化数组 */
        public MyCircleQueue(int maxsize) { 
            this.maxsize = maxsize;
            data = new int[maxsize];
        }
    
        /** * @return 判断对列是否为空 返回布尔值 */
        public boolean isEmpty() { 
            return rear == front;
        }
    
        /** * @return 判断队列是否满 返回布尔值 */
        public boolean isFull() { 
            return (rear + 1) % maxsize == front;
        }
    
        /** * @return 返回队列的有效元素 */
        public int hasElement() { 
            return (rear + maxsize - front) % maxsize;
        }
    
        /** * @return 入队操作 操作成功返回true */
        public boolean offer(int val) { 
            if (isFull()) { 
                System.out.println("队列已满");
                return false;
            }
            data[rear] = val;
            //为了防止后移溢出 需要取模
            rear = (rear + 1) % maxsize;
            return true;
    
        }
    
        /** * @return 出队操作 删除并返回出队的元素 */
        public int poll() { 
            if (isEmpty()) { 
                //为空再取 直接抛出异常
                throw new RuntimeException("队列为空");
            }
            //存放临时数据供返回
            int temp = data[front];
            front = (front + 1) % maxsize;
            return temp;
    
        }
    
        /** * * @return 出队操作 但不删除 */
        public int peek() { 
            return data[front];
        }
    
        /** * 遍历元素 */
        public void look() { 
            if (isEmpty()) { 
                //为空再取 直接抛出异常
                throw new RuntimeException("队列为空");
            }
            for (int i = front; i < front + hasElement(); i++) { 
                System.out.printf("data[%d]\t%d\t", i % maxsize, data[i % maxsize]);
            }
        }
    
    
    }

ps:慢慢来 会很快

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1d46c05a24844d4489dde9e1946be728.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/a2b41d66efc74b6abb7395eed067aab8.png