基于简单循环数组实现队列（JAVA）

236 阅读 0 评论 156 点赞

我是靠谱客的博主潇洒小蚂蚁，这篇文章主要介绍基于简单循环数组实现队列（JAVA），现在分享给大家，希望可以做个参考。

基于简单循环数组实现队列

循环数组
队列抽象数据类型的这种简单实现使用数组，在数组中，采用循环的方式则增加元素，并使用两个变量分别记录队首和队尾元素。通常，使用front变量和rear变量分别表示队列中的队首元素和队尾元素。

基于数组来存储队列中的元素，可能会出现数组被填满的情况。这时，如果执行入队操作，将抛出队列满异常，同样，如果对空队列出栈，会抛出队列空异常

代码

Tips：初始化时，front = rear = -1 代表队列为空

复制代码

/**
 * 基于简单循环数组的队列实现
 */
public class ArrayQueue {

private int front;
    private int rear;
    private int capacity;
    private int[] array;

/**
     * 私有化构造器
     *
     * @param size
     */
    private ArrayQueue(int size) {
        capacity = size;
        front = -1;
        rear = -1;
        array = new int[size];
    }

/**
     * 静态方法创建固定队列容量的队列
     *
     * @param size
     * @return
     */
    public static ArrayQueue createQueue(int size) {
        return new ArrayQueue(size);
    }

/**
     * 队列判满
     *
     * @return
     */
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

/**
     * 队列判空
     */
    public boolean isEmpty() {
        return front == -1;
    }

/**
     * 当前队列容量
     */
    public int getQueueSize() {
        return (capacity - front + rear + 1) % capacity;
    }

/**
     * 入栈
     */
    public void enQueue(int data) {
        if (isFull()) {
            throw new RuntimeException("Queue is Full!");
        }
        rear = (rear + 1) % capacity;
        array[rear] = data;
        if (front == -1) {
            front = rear;
        }
    }

/**
     * 出栈
     */
    public int deQueue() {
        Integer data = null;
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty!");
        }
        data = array[front];
        if (front == rear) {
            front = rear - 1;
        } else {
            front = (front + 1) % capacity;
        }
        return data;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * 基于简单循环数组的队列实现
 */
public class ArrayQueue {

    private int front;
    private int rear;
    private int capacity;
    private int[] array;

    /**
     * 私有化构造器
     *
     * @param size
     */
    private ArrayQueue(int size) {
        capacity = size;
        front = -1;
        rear = -1;
        array = new int[size];
    }

    /**
     * 静态方法创建固定队列容量的队列
     *
     * @param size
     * @return
     */
    public static ArrayQueue createQueue(int size) {
        return new ArrayQueue(size);
    }

    /**
     * 队列判满
     *
     * @return
     */
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    /**
     * 队列判空
     */
    public boolean isEmpty() {
        return front == -1;
    }

    /**
     * 当前队列容量
     */
    public int getQueueSize() {
        return (capacity - front + rear + 1) % capacity;
    }

    /**
     * 入栈
     */
    public void enQueue(int data) {
        if (isFull()) {
            throw new RuntimeException("Queue is Full!");
        }
        rear = (rear + 1) % capacity;
        array[rear] = data;
        if (front == -1) {
            front = rear;
        }
    }

    /**
     * 出栈
     */
    public int deQueue() {
        Integer data = null;
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty!");
        }
        data = array[front];
        if (front == rear) {
            front = rear - 1;
        } else {
            front = (front + 1) % capacity;
        }
        return data;
    }
}