队列及其Java实现

队列及其Java实现

​ 队列是一种只允许在表的前端进行删除操作且在表的后端进行插入操作的线性表。其中，执行插入操作的端叫做队尾，执行删除操作端的叫作队头。没有元素的队列叫作空队列，在队列中插入一个队列元素叫作入队，从队列中删除一个队列元素叫作出队。因为队列只允许在队尾插入，在对头删除，所以最早进入队列的元素将最先被从队列中删除，所以队列又叫作先进先出（FIFO-first in first out）线性表。

要实现一个队列，需要先实现如下核心方法。

​ add()：向队尾加入一个元素（入队），先入队列的元素在最前边。

​ poll()：删除队头的元素（出队）。

​ peek()：取出对头的元素。

队列的简单实现如下。

（1）定义队列的数据结构：

public class Queue<E> {
    private Object[] data = null;
    private int maxSize; //队列的大小
    private int front; //对头,允许删除
    private int rear; // 队尾，允许插入
    //构造函数，默认队列的大小为10
    public Queue() {
        this(10);
    }
    public Queue(int initialsize) {
        if(initialsize >= 0) {
            this.maxSize = initialsize;
            data = new Object[initialsize];
            front = rear = 0;
        } else {
            throw new RuntimeException("初始化大小不能小于0：" + initialsize);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

以上代码定义了一个名为Queue的队列，并定义了用于存储队列数据的data数组、对头位置标记front、队尾位置标记rear、队列的容量maxSize。队列的默认长度为10，在初始化时，front的位置等于rear的位置，都为0；在有新的数据加入队列时，front的值加1。

（2）向队列中插入数据：

//在队尾插入元素
    public boolean add(E e) {
        if(rear == maxSize) {
            throw new RuntimeException("队列已满，无法插入新的元素！");
        } else {
            data[rear++] = e;
            return true;
        }
    }
1
2
3
4
5
6
7
8
9

以上代码定义了add方法来向队列中插入数据，在插入前先判断队列是否满了，如果队列有空间，则通过data[rear++]=e向队尾插入数据并将队尾的指针位置加1。

（3）取走对头数据：

//删除对头的元素：出队
    public E poll() {
        if(front == rear) {
            throw new RuntimeException("空队列异常！");
        } else {
            E value = (E) data [front]; //临时保存队列front端的元素的值
            data[front++] = null;//释放队列front端的元素
            return value;
        }
    }
1
2
3
4
5
6
7
8
9
10

以上代码定义了poll方法来取走队头的数据，并将队头的数据设置为null以释放队头的位置，最后返回队头的数据。

（4）队列数据查询：

//取出对头的元素，但不删除
    public E peek(){
        if(front == rear) {
            throw new RuntimeException("空队列异常！");
        } else {
            return (E)data[front];
        }
    }
1
2
3
4
5
6
7
8

以上代码定义了peek方法来访问并返回队头的数据。

测试样例：

    public static void main(String[] args) {
        // 定义并初始化一个包含字母的String数组
        String[] letters = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M",
                "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};
        Queue<String> queue = new Queue<String>(26);
        System.out.println(queue.maxSize);
        for (String letter : letters) {
            queue.add(letter);
        }
        System.out.println(queue.peek());
        System.out.println(queue.front);
        System.out.println(queue.rear);
        for (int i = 0; i < 26; i++) {
            System.out.println(queue.poll());
        }
        System.out.println(queue.front);
        System.out.println(queue.rear);
        System.out.println(queue.peek());
        System.out.println(queue.data.length);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20