队列和环形队列

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。可以用数组或是链表来实现。

图示

队列使用数组来实现

思路

1：定义front和rear和maxsize，front是指向队列头的前一个位置，rear是指向队列尾的位置。front的默认值为-1，rear的默认值为-1。maxsize代表队列的最大长度。

2：如何判断队列为空 isEmpty() ？front == rear。

3：如何判断队列满了 isFull() ？rear == maxsize-1。

4：添加数据到队列 addQueue() ？首先判断 isFull()，如果不满，则可以添加数据，rear++，赋值给arr[rear]。

5：如何取数据 getQueue() ？首先判断isEmpty()，如果不空，则可以取数据，front++，return arr[front]。

代码实现

public class ArrayQueueDemo {
    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key = ' ';
        Scanner scanner = 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 = scanner.next().charAt(0);
            switch (key){
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    try{
                        System.out.println("请输入一个数字");
                        int value = scanner.nextInt();
                        arrayQueue.addQueue(value);
                        break;
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g':
                    try{
                        int res = arrayQueue.getQueue();
                        System.out.println("取出的数据是"+res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = arrayQueue.headQueue();
                        System.out.println("队列头的数据是"+res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    System.out.println("程序退出");
                    loop = false;
                    break;
                    default:
                        break;
            }
        }

    }
}

class ArrayQueue{
    // 表示数组的最大容量
    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; // 指向队列头部，front是指向队列头的前一个位置
        rear = -1;  // 指向队列尾部，rear指向队列尾的数据（包含最后一个数据）
    }

    // 判断队列是否是满的
    public boolean isFull(){
        return rear == maxSize-1;
    }
    // 判断队列是否为空
    public boolean isEmpty(){
        return rear == front;
    }
    // 添加数据到队列
    public void addQueue(int number){
        if(isFull()){
            System.out.println("队列满了");
            return;
        }
        rear++;
        arr[rear] = number;
    }

    //获取队列的数据，出队列
    public int getQueue(){
        if(isEmpty()){
            System.out.println("队列为空");
            throw new RuntimeException("队列为空，不能取数据");
        }
        front++;
        return arr[front];
    }

    // 显示队列的所有数据
    public void showQueue(){
       if(isEmpty()){
           System.out.println("没有数据");
           return;
       }
        for(int i =front+1;i<=rear;i++){
            System.out.print(arr[i] +"  ");
        }
    }

    // 显示队列的头数据，注意，不是取出数据
    public int headQueue(){
        if(isFull()){
            System.out.println("没有数据");
            throw new RuntimeException("没有数据异常");
        }
        return arr[front+1];
    }
}
           

缺陷

此队列只能使用一次，即队列在已经达到满了的时候，即使后面删除数据，还是不能插入数据。队列复用性不高。