資料結構和算法之數組模拟隊列

特點：先入先出(類似于銀行排隊問題)

一、數組模拟隊列

package com.company;

import java.util.Scanner;

/**
 * @author:抱着魚睡覺的喵喵
 * @date:2021/1/31
 * @description: the array simulate the queue
 */
public class ArrayQueue {
    //test array simulate queue
    public static void main(String[] args) {
        ArraySimulateQueue arraySimulateQueue = new ArraySimulateQueue(3);
        char key=' ';
        Scanner scanner = new Scanner(System.in);
        boolean flag=true;
        while (flag){
            System.out.println("s:show queue");
            System.out.println("a:add data to the queue");
            System.out.println("g:the data obtained from the queue");
            System.out.println("h:view queue header data");
            System.out.println("e:exit the program");
            key=scanner.next().charAt(0);
            switch (key){
                case 's':
                    arraySimulateQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("please entry a data!");
                    int data=scanner.nextInt();
                    arraySimulateQueue.enQueue(data);
                    break;
                case 'g':
                    try {
                        int result=arraySimulateQueue.deQueue();
                        System.out.println("the data obtained from the queue is:"+result);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int frontData=arraySimulateQueue.getFront();
                        System.out.println("the head of the queue data is:"+frontData);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    flag=false;
                    return;
                default:
                    System.out.println("the characters you entered are wrong!");
            }
        }
        System.out.println("program has exited!");
    }
}
/**
 * use array to simulate queue
 */
class ArraySimulateQueue{
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;

    public ArraySimulateQueue(int currentMaxSize){
        this.maxSize=currentMaxSize;
        this.front=-1;
        this.rear=-1;
        arr=new int[maxSize];
    }
    //determine whether the queue is full
    public boolean isFull(){
        return rear == maxSize-1;
    }
    //determine whether the queue is empty
    public boolean isEmpty(){
        return rear == front;
    }
    //enqueue
    public void enQueue(int data){
        if (isFull()){
            System.out.println("the queue is full and cannot add data!");
            return;
        }else{
            this.rear++;
            arr[rear]=data;
            System.out.println("successful data entry!");
        }
    }
    //dequeue
    public int deQueue(){
        if (isEmpty()){
            throw new RuntimeException("the queue is empty and cannot get data!");
        }else{
            this.front++;
            int result=arr[front];
            arr[front]=0;
            return result;
        }
    }
    //show data
    public void showQueue(){
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d",i,arr[i]);;
            System.out.println();
        }
    }
    public int getFront(){
        if (isEmpty()){
            throw new RuntimeException("the queue is empty and cannot get header data!");
        }else{
            return arr[front+1];
        }
    }
}      

分析缺點：

由圖可以看出使用過的記憶體單元将不能夠繼續使用，是以使用環形隊列可以解決記憶體資源浪費的問題

環形隊列

package com.company;

import java.util.Scanner;

/**
 * @author:抱着魚睡覺的喵喵
 * @date:2021/2/1
 * @description: the array simulate the circular queue
 */
public class CircleArrayQueue {
    public static void main(String[] args) {
        CircleQueue circleQueue = new CircleQueue(3);
        boolean flag = true;
        Scanner scanner = new Scanner(System.in);
        char key = ' ';
        while (flag) {
            System.out.println("s:show queue");
            System.out.println("a:add data to the queue");
            System.out.println("g:get data from the queue");
            System.out.println("h:view queue header data");
            System.out.println("e:exit the program");
            key = scanner.next().charAt(0);
            switch (key) {
                case 's':
                    circleQueue.showData();
                    break;
                case 'a':
                    System.out.println("please enter a data:");
                    int result = scanner.nextInt();
                    circleQueue.enQueue(result);
                    break;
                case 'g':
                    try {
                        System.out.printf("the data obtained from queue is:%d", circleQueue.dequeue());
                        System.out.println();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        System.out.printf("header data is:%d", circleQueue.getFront());
                        System.out.println();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    flag = false;
            }
        }
    }
}

/**
 * Circular simulate queue
 */
class CircleQueue {
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;
    private int num;

    public CircleQueue(int currentMaxSize) {
        this.maxSize = currentMaxSize;
        this.front = -1;
        this.rear = -1;
        arr = new int[maxSize];
        this.num = 0;           //record the number of array units and used to determine whether the circular queue is full or empty
    }

    //determine  whether the circular queue is full
    public boolean isFull() {
        return num == maxSize;
    }

    //determine whether the circular queue is empty
    public boolean isEmpty() {
        return num == 0;
    }

    //enqueue
    public void enQueue(int data) {
        if (isFull()) {
            System.out.println("the circular is full,unable to add data!");
        } else if ((rear + 1 == maxSize) && (!isFull())) {
            rear = 0;
            arr[rear] = data;
            num++;
        } else {
            rear++;
            arr[rear] = data;
            num++;
        }
    }

    //dequeue
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("the circular queue is empty,unable to leave the queue!");
        } else if ((front + 1 == maxSize) && (!isEmpty())) {
            front = 0;
            int result = arr[front];
            arr[front] = 0;
            num--;
            return result;
        } else {
            front++;
            int result = arr[front];
            arr[front] = 0;
            num--;
            return result;
        }
    }

    //get the circular queue header data
    public int getFront() {
        if (isEmpty()) {
            throw new RuntimeException("the circular queue is empty cannot get header data!");
        } else if (front +1 == maxSize){
            return arr[0];
        } else {
            return arr[front+1];
        }
    }

    //show data
    public void showData() {
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d", i, arr[i]);
            System.out.println();
        }
    }
}      

package com.company;

import java.util.Scanner;

/**
 * @author:抱着魚睡覺的喵喵
 * @date:2021/2/2
 * @description:
 */
public class CircleArrayQueue2 {
    public static void main(String[] args) {
        CircleQueue2 circleQueue = new CircleQueue2(3);
        boolean flag = true;
        Scanner scanner = new Scanner(System.in);
        char key = ' ';
        while (flag) {
            System.out.println("s:show queue");
            System.out.println("a:add data to the queue");
            System.out.println("g:get data from the queue");
            System.out.println("h:view queue header data");
            System.out.println("e:exit the program");
            key = scanner.next().charAt(0);
            switch (key) {
                case 's':
                    circleQueue.showData();
                    break;
                case 'a':
                    System.out.println("please enter a data:");
                    int result = scanner.nextInt();
                    circleQueue.enQueue(result);
                    break;
                case 'g':
                    try {
                        System.out.printf("the data obtained from queue is:%d", circleQueue.dequeue());
                        System.out.println();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        System.out.printf("header data is:%d", circleQueue.getFront());
                        System.out.println();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    flag = false;
            }
        }
    }
}

/**
 * Circular simulate queue
 */
class CircleQueue2 {
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;

    public CircleQueue2(int currentMaxSize) {
        this.maxSize = currentMaxSize;
        this.front = 0;
        this.rear = 0;
        arr = new int[maxSize];
    }

    //determine  whether the circular queue is full
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    //determine whether the circular queue is empty
    public boolean isEmpty() {
        return rear == front;
    }

    //enqueue
    public void enQueue(int data) {
        if (isFull()) {
            System.out.println("the circular is full,unable to add data!");
        } else {
            arr[rear] = data;
            rear = (rear + 1) % maxSize;
        }
    }

    //dequeue
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("the circular queue is empty,unable to leave the queue!");
        } else {
            int result = arr[front];
            arr[front] = 0;
            front = (front + 1) % maxSize;
            return result;
        }
    }

    //get the circular queue header data
    public int getFront() {
        if (isEmpty()) {
            throw new RuntimeException("the circular queue is empty cannot get header data!");
        } else {
            return arr[front % maxSize];
        }
    }

    //show data
    public void showData() {
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d", i, arr[i]);
            System.out.println();
        }
    }
}