欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

回顾数据结构(Java版)——写一个简单的循环队列(数组实现)

程序员文章站 2022-07-14 12:30:26
...

一个简单的循环队列,需要注意的几个问题

  1. 关于循环运算都要用到取模
  2. 循环队列的判空,判满条件要综合考虑(可以推导出来)
  3. 遍历的时候,需要是由到当前的size,然后通过取模操作取出循环队列中的值

code

package com.wrial.queue;
/*
 * @Author  Wrial
 * @Date Created in 15:40 2019/10/8
 * @Description
 */

public class CircleQueue {

    //1.定义数组和头尾指针
    int[] queue;
    int front = 0; //队头的位置
    int rear = 0;  //队尾最后一个数的后一个位置
    int capacity;

    CircleQueue() {
        queue = new int[5];
    }

    CircleQueue(int maxSize) {
        capacity = maxSize;
        queue = new int[maxSize];
    }

    //判队满  注意的是循环队列需要空出一个空间不能用来区别队空条件
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    //判队空
    public boolean isEmpty() {
        return rear == front;
    }

    //队列占用的大小
    public int size() {
        return (rear + capacity + front) % capacity;
    }

    //入队
    public void inQueue(int i) {
        //1.判断队列是否为空
        if (isFull()) {
            System.err.println("Queue Full");
            return;
        }
        //2.在队列中加值并改变指针
        queue[rear] = i;
        //此处注意要进行取模
        rear = (rear + 1) % capacity;
    }

    //出队
    public int outQueue() {
        //1.判断是否队空
        if (isEmpty()) {
            System.err.println("Queue Empty");
        }
        //2.出队并移动指针
        int value;
        value = queue[front];
        front = (front + 1) % capacity;
        return value;
    }

    //显示队列
    public void showAll() {
        for (int i = front; i < front + size(); i++) {
            System.out.printf("index%d=%d\n",i,queue[i%capacity]);
        }
    }

}

package com.wrial.queue;
/*
 * @Author  Wrial
 * @Date Created in 15:35 2019/10/8
 * @Description 数组实现循环队列
 */

/*
 众说周知,不带循环的队列只能使用一次,肯定是不能够的
 */

import java.util.Scanner;

public class CircleQueueTest {
    public static void main(String[] args) {
        CircleQueue circleQueue = new CircleQueue(5);
        boolean flag = true;
        char c = ' ';
        Scanner scanner = new Scanner(System.in);
        while (flag) {

            System.out.println("s(show)");
            System.out.println("e(exit)");
            System.out.println("a(add)");
            System.out.println("r(remove)");
            c = scanner.next().charAt(0);
            switch (c) {
                case 's':
                    circleQueue.showAll();
                    break;
                case 'e':
                    scanner.close();
                    break;
                case 'a':
                    System.out.println("输入加入的数字");
                    int i = scanner.nextInt();
                    circleQueue.inQueue(i);
                    break;
                case 'r':
                    System.out.println(circleQueue.outQueue());
                    break;
            }
        }
    }
}