队列的实现和应用

发表于 分类于 阅读次数： 本文字数： 984 阅读时长 ≈ 3 分钟

文档引用

源码实现

队列的实现

可使用数组和链表实现队列

数组

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
88
89
import java.util.ArrayList;

/**
 * 使用数组实现队列
 *
 * @author Forest Dong
 * @date 2023年12月12日 21:26
 */
public class ArrayQueue<T> {
    private ArrayList<T> list = new ArrayList<>();
    /**
     * 是否为空
     *
     * @return boolean
     * @author Forest Dong
     * @date 2023/12/12 19:43
     */
    public boolean isEmpty() {
        return list.isEmpty();
    }

    /**
     * 元素数量
     *
     * @return int
     * @author Forest Dong
     * @date 2023/12/12 19:43
     */
    public int size() {
        return list.size();
    }

    /**
     * 往栈顶添加元素
     *
     * @param e
     * @author Forest Dong
     * @date 2023/12/12 19:43
     */
    public void push(T e) {
        list.add(e);
    }

    /**
     * 从栈顶移除元素
     *
     * @return {@link T }
     * @author Forest Dong
     * @date 2023/12/12 19:43
     */
    public T pop() {
        T result = peek();
        list.remove(0);
        return result;
    }

    /**
     * 获取栈顶元素（不删除）
     *
     * @return {@link T }
     * @author Forest Dong
     * @date 2023/12/12 19:44
     */
    public T peek() {
        if (0 == size()) {
            throw new IndexOutOfBoundsException();
        }
        return list.get(0);
    }

    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        System.err.println("当前栈是否为空:" + queue.isEmpty());
        System.err.println("当前栈元素个数:" + queue.size());
        queue.push(1);
        queue.push(2);
        queue.push(3);
        System.err.println("当前栈是否为空:" + queue.isEmpty());
        System.err.println("当前栈元素个数:" + queue.size());
        System.err.println("peek第一个元素,元素值为:" + queue.peek() + ",peek后元素个数为:" + queue.size());
        System.err.println("pop第一个元素,元素值为:" + queue.pop() + ",pop后元素个数为:" + queue.size());
        System.err.println("peek第二个元素,元素值为:" + queue.peek() + ",peek后元素个数为:" + queue.size());
        System.err.println("pop第二个元素,元素值为:" + queue.pop() + ",pop后元素个数为:" + queue.size());
        System.err.println("peek第三个元素,元素值为:" + queue.peek() + ",peek后元素个数为:" + queue.size());
        System.err.println("pop第三个元素,元素值为:" + queue.pop() + ",pop后元素个数为:" + queue.size());
        System.err.println("peek第四个元素,元素值为:" + queue.peek() + ",peek后元素个数为:" + queue.size());
        System.err.println("pop第四个元素,元素值为:" + queue.pop() + ",pop后元素个数为:" + queue.size());
    }
}

链表

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/**
 * 使用链表实现队列
 *
 * @author Forest Dong
 * @date 2023年12月12日 21:10
 */
public class LinkedListQueue<T> {
    /**
     * 头节点和尾节点
     */
    private ListNode<T> head, tail;

    /**
     * 队列元素数量
     */
    private int size = 0;

    /**
     * 是否为空
     *
     * @return boolean
     * @author Forest Dong
     * @date 2023/12/12 19:43
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 元素数量
     *
     * @return int
     * @author Forest Dong
     * @date 2023/12/12 19:43
     */
    public int size() {
        return size;
    }

    /**
     * 往栈顶添加元素
     *
     * @param e
     * @author Forest Dong
     * @date 2023/12/12 19:43
     */
    public void push(T e) {
        ListNode<T> node = new ListNode<>(e);
        if (null == head) {
            head = node;
        } else if (null == tail) {
            tail = node;
            head.next = tail;
        } else {
            tail.next = node;
        }
        size++;
    }

    /**
     * 从栈顶移除元素
     *
     * @return {@link T }
     * @author Forest Dong
     * @date 2023/12/12 19:43
     */
    public T pop() {
        T result = peek();
        head = head.next();
        size--;
        return result;
    }

    /**
     * 获取栈顶元素（不删除）
     *
     * @return {@link T }
     * @author Forest Dong
     * @date 2023/12/12 19:44
     */
    public T peek() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException();
        }
        return head.value;
    }

    private static class ListNode<T> {
        private T value;

        private ListNode<T> next;

        public ListNode(T value) {
            this.value = value;
        }

        public ListNode(T value, ListNode<T> next) {
            this.value = value;
            this.next = next;
        }

        public ListNode<T> next() {
            return this.next;
        }

        public T value() {
            return this.value;
        }
    }

    public static void main(String[] args) {
        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        System.err.println("当前栈是否为空:" + queue.isEmpty());
        System.err.println("当前栈元素个数:" + queue.size());
        queue.push(1);
        queue.push(2);
        queue.push(3);
        System.err.println("当前栈是否为空:" + queue.isEmpty());
        System.err.println("当前栈元素个数:" + queue.size());
        System.err.println("peek第一个元素,元素值为:" + queue.peek() + ",peek后元素个数为:" + queue.size());
        System.err.println("pop第一个元素,元素值为:" + queue.pop() + ",pop后元素个数为:" + queue.size());
        System.err.println("peek第二个元素,元素值为:" + queue.peek() + ",peek后元素个数为:" + queue.size());
        System.err.println("pop第二个元素,元素值为:" + queue.pop() + ",pop后元素个数为:" + queue.size());
        System.err.println("peek第三个元素,元素值为:" + queue.peek() + ",peek后元素个数为:" + queue.size());
        System.err.println("pop第三个元素,元素值为:" + queue.pop() + ",pop后元素个数为:" + queue.size());
        System.err.println("peek第四个元素,元素值为:" + queue.peek() + ",peek后元素个数为:" + queue.size());
        System.err.println("pop第四个元素,元素值为:" + queue.pop() + ",pop后元素个数为:" + queue.size());
    }
}

队列的应用

  • 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
  • 各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。