type
status
date
slug
summary
tags
category
icon
password

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

数组模拟环形队列

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

解题思路

1、既然是环形队列,那就一定有头有尾,有容量
2、既然是数组实现,那一定有个算法保证可以让数组循环起来
notion image
如图所示: rear为7 ,front为0,实际的数据为7,是因为rear定义指向了最后一个元素的后一个位置,所以满数组的size变成了size-1,空出的位置来保证循环
notion image
  1. front 变量的含义做一个调整: front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 front 的初始值 = 0
  1. rear 变量的含义做一个调整:rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.rear 的初始值 = 0
  1. 当队列满时,条件是 (rear + 1) % maxSize == front 【满】
  1. 对队列为空的条件, rear == front 空
  1. 当我们这样分析, 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0
  1. 我们就可以在原来的队列上修改得到,一个环形队列

代码实现

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;           }       }   } }
 
数组实现栈 详细讲解数组实现队列 详细讲解