自定义队列

文章目录

数组队列

简述：

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:

  1. 自定义简单数组对列（有问题，不能重复使用） 
package com.njau.queue;

import java.util.Scanner;

/** * @author 张文军 * @Description:arrayQueue数组队列 * @Company:南京农业大学工学院 * @version:1.0 * @date 2019/8/249:06 */
public class ArrayQueue {
    int maxiSize;
    int front;
    int rear;
    int[] arr;

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

    }

    public Boolean isFull() {
        return rear == maxiSize - 1;
    }

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

    public void addQueue(int n) {
        if (isFull()) {
            System.out.println("queue hase full !");
            return;
        } else {
            arr[++rear] = n;
        }
    }

    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("queue is empty !");
        } else {
            return arr[++front];
        }
    }

    public void showQueue() {
        if (!isEmpty()) {
            for (int i = 0; i < arr.length; i++) {
                System.out.printf("arr[%d] = %d\n", i, arr[i]);
            }
        } else {
            System.out.println("queue is empty !");
        }
    }

    public int getQueueHead() {
        if (isEmpty()) {
            throw new RuntimeException("queue is empty!");
        } else {
            return arr[front + 1];
        }
    }


	/** * 测试 */
    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue(3);
        Scanner scanner = new Scanner(System.in);
        Boolean loop = true;
        while (loop) {
            System.out.println("s 展示");
            System.out.println("a 添加");
            System.out.println("g 取数据");
            System.out.println("h 显示头数据");
            System.out.println("e 退出");
            char key = scanner.next().charAt(0);
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入数据：");
                    int i = scanner.nextInt();
                    queue.addQueue(i);
                    break;
                case 'g':
                    try {
                        int queue1 = queue.getQueue();
                        System.out.println("取出的数据是:" + queue1);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int queueHead = queue.getQueueHead();
                        System.out.println("头数据:" + queueHead);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("exit !");

    }

}

数组环形队列

上面简介和用数组简单实现了一下队列，但这种队列依然存在问题，问题就是用数组简单实现的队列会存在假溢出现象（即：在数据退出队列时，虽然数据未满，但是队列的 rear 已经是数组的大小，即显示已满。故不能继续插入数据 ），这样会极大的降低了数组的利用，所以，在这里我将会用数组实现一个环形队列，以解决这种问题。

  • 首先在这里，声明了一个容量大小为8的数组，并标出了索引0-7，然后使用front和 rear 分别来表示队列的，队首和队尾；在下图中，front 和 rear 的位置一开始都指向是了索引0的位置，这意味着当front == rear 的时候 队列为空 ，务必牢记这一点，以便区分后面介绍队列快满时的临界条件

  • front：表示队列队首，始终指向队列中的第一个元素（当队列空时，front指向索引为0的位置）

  • rear ：表示队列队尾，始终指向队列中的最后一个元素的下一个位置

  • 元素入队，维护rear 的位置，进行rear ++操作

  • 元素出队，维护front的位置，进行front++操作

按照上面的front和rear的意思，对队列的维护即对是简单的++操作，即：入队就是将rear++，front不变，出队就是front++，rear不变。
即如下图所示：

然而，如果再向后面添加，即当出现

即当rear指向数组的最后，而且队列也已经有元素出队时，应为rear不能再向后移动，所以虽然数组有空的空间，但却不能插入数据，此时就出现了数组假溢出现象。然而，如果rear的位置用（rear+1)% maxSize ，则就会避免出现这种情况，即我们将现在的数组看成是一个环，当rear=front=0时，数组为空，插入一条数据，rear = （rear+1 ）%maxSize = 1%8= 1； 当队列上图情况时，即rear已经是移动到数组的最后一个位置，而且有数据已经出队时，这时插入数据时，rear = （rear+1 ）% maxSize = （7+1）%8 = 0，即循环到了下一个位置。同理，front的位置决定也是：front= (front+1)%maxSize，在这种情况下，必须要牺牲一个数组空间来（用于方便判断），而且判断队列是否已满的条件是rear==(front+1)%maxSize，为空rear==front ==0；

代码实现如下：

package com.njau.queue;

/** * @author 张文军 * @Description:数组循环队列 * @Company:南京农业大学工学院 * @version:1.0 * @date 2019/9/23:42 */
public class ArrayCycleQueue {
    /** * 数组大小 */
    int maxiSize;
    /** * 指向队列的头元素 */
    int front;
    /** * 指向队列的最后一个元素的下一个元素 */
    int rear;
    /** * 数组 */
    int[] arr;

    public ArrayCycleQueue(int maxiSize) {
        this.maxiSize = maxiSize;
        arr = new int[maxiSize];
        front = 0;
        rear = 0;

    }

    public Boolean isFull() {
        return front == (rear + 1) % maxiSize;
    }

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

    public void addQueue(int n) {
        if (isFull()) {
            System.out.println("queue is full !");
            return;
        } else {
            arr[rear] = n;
            rear = (rear + 1) % maxiSize;
        }
    }

    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("queue is empty !");
        } else {
            int popData = arr[front];
            front = (front + 1) % maxiSize;
            return popData;
        }
    }

    public void showQueue() {
        if (!isEmpty()) {
            for (int i = 0; i < arr.length; i++) {
                System.out.printf("arr[%d] = %d\n", i, arr[i]);
            }
        } else {
            System.out.println("queue is empty !");
        }
    }

    public int getQueueHead() {
        if (isEmpty()) {
            throw new RuntimeException("queue is empty!");
        } else {
            return arr[front];
        }
    }

}

测试：

    public static void main(String[] args) {
        ArrayCycleQueue queue = new ArrayCycleQueue(3);
        Scanner scanner = new Scanner(System.in);
        Boolean loop = true;
        while (loop) {
            System.out.println("s 展示");
            System.out.println("a 添加");
            System.out.println("g 取数据");
            System.out.println("h 显示头数据");
            System.out.println("e 退出");
            char key = scanner.next().charAt(0);
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入数据：");
                    int i = scanner.nextInt();
                    queue.addQueue(i);
                    break;
                case 'g':
                    try {
                        int queue1 = queue.getQueue();
                        System.out.println("取出的数据是:" + queue1);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int queueHead = queue.getQueueHead();
                        System.out.println("头数据:" + queueHead);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("exit !");

    }