数组实现环形队列 详细讲解(java)

数组实现环形队列 详细讲解(java),第1张

数组实现环形队列 详细讲解 数组模拟环形队列

对前面的数组模拟队列的优化,将数组看做是一个环形的。(通过取模的方式来实现即可)

解题思路

1、既然是环形队列,那就一定有头有尾,有容量

2、既然是数组实现,那一定有个算法保证可以让数组循环起来


如图所示:
rear为7 ,front为0,实际的数据为7,是因为rear定义指向了最后一个元素的后一个位置,所以满数组的size变成了size-1,空出的位置来保证循环

  1. front 变量的含义做一个调整: front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 front 的初始值 = 0
  2. rear 变量的含义做一个调整:rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定**.rear 的初始值 = 0**
  3. 当队列满时,条件是 (rear + 1) % maxSize == front 【满】
  4. 对队列为空的条件, rear == front 空
  5. 当我们这样分析, 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0
  6. 我们就可以在原来的队列上修改得到,一个环形队列
代码实现
package com.qf;

import java.util.Scanner;

public class CircleQueue {
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;

    /**
     * 环形队列的实现
     */

    //初始化环型队列
    public CircleQueue(int maxSize){
        this.arr=new int[maxSize];
        this.maxSize=maxSize;
        this.front=0;
        this.rear=0;
    }

    //队列是否已满
    public boolean isFull(){
        return (rear+1)%maxSize==front;
    }

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

    //入队
    public void addQueue(int num){
        if (isFull()){
            System.out.println("队列已满,请稍等~~~");
        }else{
            arr[rear]=num;
            rear=(rear+1)%maxSize;
        }
    }

    //出队
    public int outQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空,不能出队~~");
        }
        int outNum=arr[front];
        System.out.println("出队的数值为:"+outNum);
        front=(front+1)%maxSize;
        return outNum;
    }

    //循环队列有效元素
    public void showQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空~~");
        }
        for (int i = front; i < front+size(); i++) {
            System.out.printf(" " +arr[i%maxSize]);
        }
    }

    //得到对头的元素
    public int getHeader(){
        if (isEmpty()){
            throw new RuntimeException("队列为空~~");
        }
        System.out.println("对头元素:"+arr[front%maxSize]);
        return arr[front%maxSize];
    }

    //得出有效元素的个数
    public int size(){
        return (rear+maxSize-front)%maxSize;
    }

    public static void main(String[] args) {
        CircleQueue queue = new CircleQueue(4);
        boolean loop=true;
        char sc=' ';
        while (loop){
            System.out.println("e 跳出循环");
            System.out.println("a 入队");
            System.out.println("o 出队");
            System.out.println("s 循环队列");
            System.out.println("h 展示队头");
            Scanner systemPut=new Scanner(System.in);
            sc=systemPut.next().charAt(0);
            switch (sc){
                case 'a':
                    System.out.println("请输入数据:");
                    Scanner addNum=new Scanner(System.in);
                    int num = addNum.nextInt();
                    queue.addQueue(num);
                    break;
                case 'o':
                    queue.outQueue();
                    break;
                case 's':
                    queue.showQueue();
                    break;
                case 'h':
                    queue.getHeader();
                    break;
                case 'e':
                    loop=false;
                    break;
                default :
                    break;
            }
        }

    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/726100.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-26
下一篇 2022-04-26

发表评论

登录后才能评论

评论列表(0条)

保存