首页 数据结构和算法

循环队列队头指针rear = MaxSize -1 后,再前进一个位置就自动到0.

核心算法:

[scode type="blue"]
初始时:rear = front = 0
队首指针进1:front = (front + 1)%MaxSize
队尾指针进1:rear = (rear + 1)%MaxSize
队列长度:(rear + MaxSize - front)%MaxSize
[/scode]

判断队空还是队满,有三种方案:
① 牺牲一个单元来区分队空和队满
② 类型中增设表示元素个数的成员
③ 类型中增设tag成员

常用第一种方案来实现,即牺牲一个单元来区分队空和队满,入队时少用一个队列单元,约定以队头指针在队尾指针的下一位置作为队满的标志。因为如果不这样做,rear == front就无法判断是空还是满了。

循环队列的实现思路

采用第一种方案时的核心算法:

[scode type="blue"]
队满条件:(rear + 1)%MaxSize == front
队空条件:front == rear
队列中元素的个数:(rear + MaxSize - front)%MaxSize
[/scode]

代码实现

package cn.kuetr.queue;

import java.util.Scanner;

public class CircleArrayQueueDemo {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("测试数组模拟环形队列");
        // 创建一个队列s
        CircleArray arrayQueue = new CircleArray(4); //队列有效数据最大为3
        char key;// 接收用户输入
        Scanner scan = new Scanner(System.in);
        boolean loop = true;
        // 输出一个菜单
        while (loop) {
            System.out.println("s(show):显示队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列中取出数据");
            System.out.println("h(head):查看队列头的数据");
            key = scan.next().charAt(0); // 接收一个字符
            switch (key) {
            case 's':
                arrayQueue.showQueue();
                break;
            case 'a':
                System.out.println("请输入一个数:");
                int value = scan.nextInt();
                arrayQueue.addData(value);;
                break;
            case 'g':
                try {
                    int res = arrayQueue.getData();
                    System.out.printf("取出的数据是%d\n", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());// TODO: handle exception
                }
                break;
            case 'h':
                try {
                    int res = arrayQueue.headQueue();
                    System.out.printf("队列头的数据是:%d", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());// TODO: handle exception
                }
                break;
            case 'e': // 退出
                scan.close();
                loop = false;
                break;
            default:
                break;
            }
        }
        System.out.println("程序退出");
    }

}

class CircleArray {
    private int maxSize; // 表示数组的最大容量
    private int front; // 表示头结点

    // 表示队列的最后一个元素的后一个位置,
    // 因为希望空出一个单位用于进行判断满还是空
    private int rear;
    private int arr[]; // 该数组用于存放数据

    public CircleArray(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        // 下面两个可以不写
        front = 0;
        rear = 0;
    }

    private boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    private boolean isEmpty() {
        return rear == front;
    }

    public void addData(int data) {
        if (isFull()) {
            System.out.println("队列满,不能加入数据");
            return;
        }
        arr[rear] = data;
        // 将rear指针后移,但必须取模
        rear = (rear + 1) % maxSize;
    }

    public int getData() {
        if (isEmpty()) {
            throw new RuntimeException("对不起,数列为空");
            // System.out.println("对不起,数列为空");

        }
        int tmp = arr[front];
        front = (front + 1) % maxSize; // 考虑到rear会再到front前面
        return tmp;
    }

    // 显示队列所有数据
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("对不起,队列为空");
            return;
        }
        for (int i = front; i < front + size(); i++) {
            //由于是环形,可能会返回,数组会越界,所以应当取模
            System.out.printf("arr[%d] = %d\n", i % maxSize, arr[i % maxSize]);
        }
    }

    // 求出队列中有效数据的个数
    public int size() {
        return (rear - front + maxSize) % maxSize;
    }
    
    //显示队列的头数据
    public int headQueue() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空,没有数据");
        }
        return arr[front];
    }
}



文章评论