---

提示：以下是本篇文章正文内容，Java系列学习将会持续更新

一、基本概念

队列(queue)：在队首出队，队尾入队，先进先出的线性表。

核心操作：

• 入队 offer
• 出队 poll
• 返回队首元素 peek

队列的子类：

• 基础队列 - FIFO
• 基于优先级的队列 – 按照优先级大小出队
• 循环队列 – 基于数组实现的
• 双端队列

回到目录…

二、代码实现

设计一个接口

public interface Queue {
    //入队
    boolean offer(E val);
    //出队
    int poll();
    //返回队首元素
    int peek();
    //判断队列是否为空
    boolean isEmpty();
}
1
2
3
4
5
6
7
8
9
10

基于链表的基础队列

/**
 * 基于链表实现的基础队列
 */
public class MyQueue implements Queue {

    //----链表的每个节点----
    private class Node {
        int val;
        Node next;
        Node(int val) {
            this.val = val;
        }
    }
    //---------------------

    private int size; // 元素个数
    private Node head; // 队首
    private Node tail; // 队尾

    @Override
    public void offer(int val) {
        Node node = new Node(val);
        if(head == null){
            head = tail = node;
        }else{
            //尾插
            tail.next = node;
            tail = node;
        }
        size ++;
    }

    @Override
    public int poll() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot poll!");
        }
        Node node = head;
        head = head.next;
        node.next = null;
        size --;
        return node.val;
    }

    @Override
    public int peek() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot peek!");
        }
        return head.val;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        for(Node x = head; x != null; x = x.next) {
            sb.append(x.val);
            if(x.next != null){
                sb.append(" ,");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
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

回到目录…

基于数组的环形队列

/**
 * 基于数组实现的环形队列
 */
public class LoopQueue implements Queue {

    private int length; // 队列长度
    private int head; // 指向队首元素
    private int size; // 有效元素个数
    private int[] arr; // 定义数组

    public LoopQueue(int length) {
        this.length = length;
        arr = new int[length];
    }

    @Override
    public boolean offer(int val) {
        if(size == length) {
            throw new StackOverflowError("队列已满");
        }
        arr[(head + size) % length] = val;
        size ++;
        return true;
    }

    @Override
    public int poll() {
        if(size == 0){
            throw new NoSuchElementException("队列为空");
        }
        int ret = arr[head];
        head = (head + 1) % length;
        size --;
        return ret;
    }

    @Override
    public int peek() {
        if(size == 0){
            throw new NoSuchElementException("队列为空");
        }
        return arr[head];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(arr[(head + i) % length]);
            sb.append(", ");
        }
        sb.replace(sb.length() - 2, sb.length(), "]");
        return sb.toString();
    }
}
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

回到目录…

三、java.util包下的队列

定义一个Queue队列：

// 方法一：实现Queue接口，基础队列
	Queue<Integer> queue1 = new ArrayDeque<>();
	Queue<Integer> queue2 = new LinkedList<>();
// 方法二：实现Deque接口，双端队列
	Deque<Integer> deq1 = new ArrayDeque<>();
	Deque<Integer> deq2 = new LinkedList<>();
1
2
3
4
5
6

队列的操作：

// ①插入元素
	boolean offer(E e); // 队尾入队
// ②删除元素
	E poll(); // 队首出队
// ③返回队首/栈顶元素
	E peek();
// ④返回元素个数
	int size();
1
2
3
4
5
6
7
8

回到目录…

---

总结:
提示：这里对文章进行总结：
以上就是今天的学习内容，本文是Java数据结构的学习，认识了队列，自己实现了基础队列和环形队列，java.util包下的队列集合用法。之后的学习内容将持续更新！！！