队列

收录于

学习数据结构与算法

2021-05-17 14:29 · 阅读时长10分钟

队列是一种线性存储结构，但是只能从队列前端front添加或入队，从队列尾端rear移除或出队数据。队列具有先进先出FIFO的特点。

队列是一种抽象的数据结构，可以用数组或者链表来实现队列。例如，[1,2,3,4,5,6,7,8,9] 使用队列来存储的示意图。

队列

等待开始

前端
1
2
3
4
5
6
7
8
9
后端
10

1/22

队列的应用

当某共享资源使用（或者处理）数量大于限制数量的时侯，这些请求（或者任务）需要先等待，待资源可用时按照先到先得原则处理，这种情况，这些请求（或者任务）经常会使用队列来保存。

CPU调度的任务队列
Web服务器请求队列
键盘按键事件队列
多个系统（应用）之间的通信的消息队列

另外，在广度优先搜索算法中我们也经常会用到队列。

常见的队列有以下这些

双端队列，两端都可以入队和出队的队列。
循环队列，在使用数组实现队列时，多次入队出队之后，前端和后端都指向数组末尾，而数组实际上使用率很低，所以引入循环队列，在数组还有空间的时候，继续在数组开始入队元素。
优先队列，每个队列元素都有一个优先级，根据优先级来确定出队的顺序。优先队列内部一般是使用堆来实现。

查看二叉堆课程

注释

1/**
2 * 自定义数组实现的双端循环队列
3 */
4class ZXDeque<T> {
5
6    private final int capacity;
7    private final Object[] data;
8    private int front;
9    private int rear;
10
11    public ZXDeque(int capacity) {
12        this.capacity = capacity + 1;
13        this.data = new Object[this.capacity];
14        this.front = 0;
15        this.rear = 0;
16    }
17
18    public boolean addFirst(T value) {
19        if (isFull()) {
20            return false;
21        }
22        front = (front - 1 + capacity) % capacity;
23        data[front] = value;
24        return true;
25    }
26
27    public boolean addLast(T value) {
28        if (isFull()) {
29            return false;
30        }
31        data[rear] = value;
32        rear = (rear + 1) % capacity;
33        return true;
34    }
35
36    public boolean removeFirst() {
37        if (isEmpty()) {
38            return false;
39        }
40        front = (front + 1) % capacity;
41        return true;
42    }
43
44
45    public boolean removeLast() {
46        if (isEmpty()) {
47            return false;
48        }
49        rear = (rear - 1 + capacity) % capacity;
50        return true;
51    }
52
53    @SuppressWarnings("unchecked")
54    public T getFront() {
55        if (isEmpty()) {
56            return null;
57        }
58        return (T) data[front];
59    }
60
61    @SuppressWarnings("unchecked")
62    public T getRear() {
63        if (isEmpty()) {
64            return null;
65        }
66        return (T) data[(rear - 1 + capacity) % capacity];
67    }
68
69    public boolean isEmpty() {
70        return front == rear;
71    }
72
73    public boolean isFull() {
74        return (rear + 1) % capacity == front;
75    }
76
77    @Override
78    public String toString() {
79        StringBuilder sb = new StringBuilder("[");
80        for (int i = front; i != rear; i = (i + 1) % data.length) {
81            sb.append(data[i]);
82            if (i != rear - 1) {
83                sb.append(",");
84            } else {
85                sb.append("]");
86            }
87        }
88        return sb.toString();
89    }
90}
91
92public class Main {
93
94    public static void main(String[] args) {
95        ZXDeque<Integer> queue = new ZXDeque<>(5);
96        assert queue.isEmpty();
97        queue.addLast(3);
98        queue.addFirst(2);
99        queue.addFirst(1);
100        queue.addLast(4);
101        queue.addLast(5);
102        assert queue.isFull();
103        System.out.println(queue);
104        assert queue.getRear() == 5;
105        assert queue.getFront() == 1;
106        queue.removeFirst();
107        queue.removeLast();
108        System.out.println(queue);
109    }
110}
111

/**
 * 自定义数组实现的双端循环队列
 */
class ZXDeque<T> {

private final int capacity;
    private final Object[] data;
    private int front;
    private int rear;

public ZXDeque(int capacity) {
        this.capacity = capacity + 1;
        this.data = new Object[this.capacity];
        this.front = 0;
        this.rear = 0;
    }

public boolean addFirst(T value) {
        if (isFull()) {
            return false;
        }
        front = (front - 1 + capacity) % capacity;
        data[front] = value;
        return true;
    }

public boolean addLast(T value) {
        if (isFull()) {
            return false;
        }
        data[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

public boolean removeFirst() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

public boolean removeLast() {
        if (isEmpty()) {
            return false;
        }
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }

@SuppressWarnings("unchecked")
    public T getFront() {
        if (isEmpty()) {
            return null;
        }
        return (T) data[front];
    }

@SuppressWarnings("unchecked")
    public T getRear() {
        if (isEmpty()) {
            return null;
        }
        return (T) data[(rear - 1 + capacity) % capacity];
    }

public boolean isEmpty() {
        return front == rear;
    }

public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

@Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            sb.append(data[i]);
            if (i != rear - 1) {
                sb.append(",");
            } else {
                sb.append("]");
            }
        }
        return sb.toString();
    }
}

public class Main {

public static void main(String[] args) {
        ZXDeque<Integer> queue = new ZXDeque<>(5);
        assert queue.isEmpty();
        queue.addLast(3);
        queue.addFirst(2);
        queue.addFirst(1);
        queue.addLast(4);
        queue.addLast(5);
        assert queue.isFull();
        System.out.println(queue);
        assert queue.getRear() == 5;
        assert queue.getFront() == 1;
        queue.removeFirst();
        queue.removeLast();
        System.out.println(queue);
    }
}

注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main

面试题 17.14. 最小K个数

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

提示：

0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))

题目链接：https://leetcode-cn.com/problems/smallest-k-lcci

注释

这道题最容易想到的就是先排序，然后返回最小的k个数。但是实际面试中，面试官可能还会问，如果数据特别大，大到无法直接对整个数组进行排序，该怎么办？

我们可以将数组中前k个数加入到优先队列中，然后遍历数组中剩下的元素，如果元素小于队列中最大的数，则将最大的数出队，然后将元素入队，如果大于则跳过，直到遍历完成。

用栈实现队列

用栈来实现队列先进先出队列。栈的特点先进后出，怎么才能实现先进先出？

Queue队列双端队列循环队列

队列

学习数据结构与算法

队列的应用

面试题 17.14. 最小K个数

用栈实现队列

栈

二叉树