三种队列（线性队列、循环队列、动态队列）

   队列
   1.线性队列
   2.循环队列
   3.动态队列

队列接口

public interface Queue {
    void put(char a);
    char get();
    void show();
}

线性队列

//线性队列
public class Queue1 implements Queue {
    private int i;
    private int j;
    private char[] arr;
    Queue1(int size){
        arr = new char[size];
        i = j = 0;
    }
    @Override
    public void put(char a) {
        if(a == ' '){
            System.out.println("该元素非法");
        }else if(i == arr.length) {
            System.out.println("线性队列已满，添加元素失败！");
        }else arr[i++] = a;

    }

    @Override
    public char get() {
        if(j == arr.length) {
            System.out.println("线性队列无元素，获取元素失败！");
            return '-';
        }else {
            char b = arr[j];
            arr[j++] = ' ';
            return b;
        }
    }

    @Override
    public void show() {
        System.out.println("线性队列元素为：");
        for(char v:arr){
            System.out.println(v + "\t\t");
        }
        System.out.println("————————————————————————");
    }
}

循环队列

//循环队列
public class Queue2 implements Queue{
    private int i;
    private int j;
    private char[] arr;
    Queue2(int size){
        arr = new char[size];
        i = j = 0;
    }
    @Override
    public void put(char a) {
        if (a == ' ') {
            System.out.println("该元素非法");
        }else {
            if (i == arr.length) {
                i = 0;
            }
            arr[i++] = a;
        }
    }

    @Override
    public char get() {
        if (i == arr.length) {
            j = 0;
        }
        char b = arr[j];
        arr[j++] = ' ';
        return b;
    }

    @Override
    public void show() {
        System.out.println("循环队列元素为：");
        for(char v:arr){
            System.out.println(v + "\t\t");
        }
        System.out.println("————————————————————————");
    }
}

动态队列

import java.util.ArrayList;
import java.util.Arrays;

//动态队列，自动扩展
public class Queue3 implements Queue{
    private int i;
    private int j;
    private char[] charArr;
    private ArrayList<Character> charArraylist;
    private char[] newArr;
    Queue3(int size){
        charArr = new char[size];
        i = j = 0;
    }
    @Override
    //charArr出队更新 ---> newArr出队更新
    public void put(char a) {
        if (a == ' ') {
            System.out.println("元素非法");
        }else{
            if(i < charArr.length){
                charArr[i++] = a;//如果未超过原数组长度，则无需扩展，不需要ArrayList
            }else{
                if (i == charArr.length){//表示第一个超过数组长度的字符进入队列，创建扩展ArrayList
                charArraylist = new ArrayList<Character>();
                for(int m = 0;m < charArr.length;m++){//将原长度的数组内容添加到ArrayList中，出队后更新在charArr中
                    charArraylist.add(Character.valueOf(charArr[m]));
                }
                charArraylist.add(Character.valueOf(a));//将新入队的元素也添加到ArrayList中
                }else{//表示不是第一此扩展队列
                    charArraylist.clear();//先将原ArrayList的元素清除，这是为了动态更新数组，保证出队更新
                    for(int m = 0;m < newArr.length;m++){//重新将newArr中的元素添加在ArrayList中
                        charArraylist.add(Character.valueOf(newArr[m]));
                    }
                    charArraylist.add(Character.valueOf(a));
                }
                //i按照数字顺序逐一递增，所以以下程序在第一个超长度元素入队之后执行第一次，将ArrayList中的元素转化为Char[]
                Object[] newC = charArraylist.toArray();
                Character[] newChar = Arrays.copyOf(newC,newC.length,Character[].class);
                newArr = new char[newChar.length];
                for(int m = 0 ;m < newChar.length;m++){
                    newArr[m] = newChar[m].charValue();
                }
                i++;
            }
        }
    }

    @Override
    public char get() {
        char b;
        if(i-1 < charArr.length){
            b = charArr[j];
            charArr[j++] = ' ';
        }else{
            b = newArr[j];
            newArr[j++] = ' ';
        }
        return b;
    }

    @Override
    public void show() {
        System.out.println("动态队列元素为：");
        if(i-1 < charArr.length){
            for(char v:charArr){
                System.out.println(v + "\t\t");
            }
        }else{
            for(char v:newArr){
                System.out.println(v + "\t\t");
            }
        }
        System.out.println("————————————————————————");
    }
}

main方法

public class QueueDemo {
    public static void main(String[] args) {
        Queue1 q1 = new Queue1(4);
        q1.put('1');
        q1.put('2');
        q1.put('3');
        q1.put('4');
        q1.show();
        System.out.println("取出：" + q1.get());
        q1.show();
        q1.put('5');
        q1.put(' ');


        Queue2 q2 = new Queue2(4);
        q2.put('a');
        q2.put('b');
        q2.put('c');
        q2.put('d');
        q2.show();
        System.out.println("取出：" + q2.get());
        q2.show();
        q2.put('e');
        q2.show();


        Queue3 q3 = new Queue3(4);
        q3.put('9');
        q3.put('8');
        q3.put('7');
        q3.put('6');
        q3.show();

        q3.put('5');
        q3.show();
        System.out.println("取出：" + q3.get());
        q3.show();

        q3.put('4');
        q3.show();
        q3.put('4');
        q3.show();
        System.out.println("取出：" + q3.get());
        q3.show();
    }
}