526互联

队列和循环队列(ArrayQueueAndCircleQueue)

发布时间 2023-11-22 11:20:08作者: MGLblog

队列

数组队列

1.初始化队列

private int maxsize;//最大长度
    private int front;//指向队首的前一个位置
    private int rear;//指向队尾
    private int[] arr;

    public ArrayQueue(int maxsize) {
        this.maxsize = maxsize;
        arr = new int[maxsize];
        front = -1;
        rear = -1;
    }

2.判断是否队列已满

//    判断是否队列已满
public boolean isFull() {
    return rear == maxsize - 1;
}

3.判断队列是否为空

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

4.入队

//    入队
public void addQueue(int n) {
    if (isFull())
        throw new RuntimeException("队列已满");
    arr[++rear] = n;
}

5.出队

//    获取数据，出队
public int getQueue() {
    if (isEmpty())
        throw new RuntimeException("队列为空~~");
    return arr[++front];
}

6.显示队列所有数据

//    显示队列所有数据
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]);
    }
}

7.获取队头数据

//    获取队头数据
public int headQueue() {
    if (isEmpty())
        throw new RuntimeException("队列为空~~");
    return arr[front + 1];
}

8.测试代码

/**
 * @author 缪广亮
 * @version 1.0
 * 数组队列
 */
public class ArrayQueueDemo {
    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(3);
        Scanner scanner = new Scanner(System.in);
        char key = ' ';//接收用户输入
        boolean loop = true;
        while (loop) {
            System.out.println("======a(add)======");
            System.out.println("======g(get)======");
			System.out.println("======h(head)======");
            System.out.println("======s(show)======");
            System.out.println("======e(exit)======");
            System.out.print("请输入菜单选项中的首字母操作：");
            key = scanner.next().charAt(0);
            switch (key) {
                case 'a':
                    try {
                        System.out.println("请输入加入队列的一个数：");
                        int value = scanner.nextInt();
                        arrayQueue.addQueue(value);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g':
                    int res = 0;
                    try {
                        res = arrayQueue.getQueue();
                        System.out.println("取出的数据是：" + res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int head = arrayQueue.headQueue();
                        System.out.println("队头数据: " + head);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    System.out.println("你的输入有误，请重新输入！");
            }
        }
        System.out.println("程序退出~~~");
    }
}

循环队列

1.初始化队列

private int maxsize;
//指向队首元素，即队列的第一个元素front=0
private int front;
//指向队列的最后一个元素的后一个位置，空出一个空间为约定rear=(rear+1)%maxsize
private int rear;
private int[] arr;

public CircleQueue(int maxsize) {
    this.maxsize = maxsize;
    arr = new int[maxsize];
    front=0;
    rear=0;
}

2.判断是否队列已满

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

3.判断队列是否为空

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

4.入队

//    入队
    public void addQueue(int n) {
        if (isFull())
            throw new RuntimeException("队列已满");
        arr[rear] = n;
//        指向队列的最后一个元素的后一个位置，考虑取模
        rear = (rear + 1) % maxsize;
    }

5.获取队列的数据，出队列

 //    获取队列的数据，出队列
    public int getQueue() {
        if (isEmpty())
            throw new RuntimeException("队列为空~~");
//        分析出front是指向队列的第一个元素
//        先把front对应的值保留到一个临时变量
//        将临时变量返回
        int value = arr[front];
        //        将front后移，考虑取模
        front = (front + 1) % maxsize;
        return value;

    }

6.显示队列所有数据

//    显示队列所有数据
    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)]);
        }
    }

7.当前队列中有效个数

//    当前队列中有效个数
public int size() {
    return (rear + maxsize - front) % maxsize;
}

8.获取队头和队尾数据

//    获取队头数据
    public int headQueue() {
        if (isEmpty())
            throw new RuntimeException("队列为空~~");
        return arr[front];
    }
//    获取队尾元素
    public int lastQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空~~");
        }
        return arr[(rear-1+maxsize)%maxsize];
    }

8.测试代码

/**
 * @author 缪广亮
 * @version 1.0
 * 循环队列
 */
@SuppressWarnings({"all"})
public class CircleQueueDemo {
    public static void main(String[] args) {
        CircleQueue circleQueue = new CircleQueue(4);
        Scanner scanner = new Scanner(System.in);
        char key = ' ';//接收用户输入
        boolean loop = true;
        while (loop) {
            System.out.println("======a(add)======");
            System.out.println("======g(get)======");
            System.out.println("======h(head)======");
            System.out.println("======s(show)======");
            System.out.println("======l(last)======");
            System.out.println("======e(exit)======");
            System.out.print("请输入菜单选项中的首字母操作：");
            key = scanner.next().charAt(0);
            switch (key) {
                case 'a':
                    try {
                        System.out.println("请输入加入队列的一个数：");
                        int value = scanner.nextInt();
                        circleQueue.addQueue(value);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g':
                    int res = 0;
                    try {
                        res = circleQueue.getQueue();
                        System.out.println("取出的数据是：" + res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int head = circleQueue.headQueue();
                        System.out.println("队头数据: " + head);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 's':
                    circleQueue.showQueue();
                    break;
                case 'l':
                    try {
                        int last = circleQueue.lastQueue();
                        System.out.println("取得的队尾数据："+last);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    System.out.println("你的输入有误，请重新输入！");
            }
        }
        System.out.println("程序退出~~~~");
    }
}