1. 内容大纲

本章节的代码：https://github.com/wicksonZhang/data-structure/tree/main/4-Queue

队列（Queue）

2. 基础知识

2.1. 什么是队列

队列：是一种线性表的数据结构，队列有头尾两端，分别是队头和队尾。元素会先从对头进行入队，再从队尾进行出队。遵循 First In First Our 原则。

image-20231121230335831

2.2. 队列的优缺点

优点

  1. 开发简单：队列主要是基于链表或者动态数组，所以开发简单易懂。
  2. FIFO原则：队列遵循先进先出原则，保证了数据处理的顺序性和稳定性。
  3. 代码解耦：例如我们平时常见的消息队列其实底层采用的数据结构就是队列，而消息队列的最大一个特点就是解耦。

缺点

  1. 不支持随机访问：由于队列基于链表，所以也导致了队列不支持随机访问。

2.3. 队列的分类

  1. 普通队列（Basic Queue）： 这是最基本的队列形式，按照先进先出（FIFO）的原则管理数据。
  2. 双端队列（Deque）： 双端队列支持在队列的两端进行插入和删除操作。可以从前端或后端插入/删除元素，具有更灵活的操作特性。
  3. 循环队列（Circular Queue）： 循环队列是一种特殊类型的队列，在队列的基础上做了优化，通过循环利用数组空间来避免数组元素移动的开销。

2.4. 生活中对应的场景

  1. 排队场景：例如我们平时排队，遵循的就是 FIFO 原则。
  2. 水管：我们平时用的水管也是遵循 FIFO 原则。

3. 普通队列

3.1. 接口设计

image-20231121233625431

  • Queue<E>.java

我们的普通队列主要是基于链表进行实现，所以还是要基于以前的代码。

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
/**
 * 队列
 *
 * @param <E>
 */
public class Queue<E> {

    private List<E> list = new LinkedList<>();

    // 元素的数量
    public int size(){}

    // 是否为空
    public boolean isEmpty(){}

    // 入队
    public void enQueue(E element){}

    // 出队
    public E deQueue(){}

    // 获取队列的头元素
    public E front(){}

}

3.2. 代码实现

3.2.1. 初始化成员变量

1
private List<E> list = new LinkedList<>();

3.2.2. 元素的数量

1
2
3
4
5
6
7
8
/**
 * 元素的数量
 *
 * @return int
 */
public int size() {
    return list.size();
}

3.2.3. 是否为空

1
2
3
4
5
6
7
8
/**
 * 是否为空
 *
 * @return boolean
 */
public boolean isEmpty() {
    return list.isEmpty();
}

3.2.4. 清空元素

1
2
3
4
5
6
/**
 * 清空元素
 */
public void clear() {
    list.clear();
}

3.2.5. 入队

动画

1
2
3
4
5
6
7
8
/**
 * 入队
 *
 * @param element 元素
 */
public void enQueue(E element) {
    list.add(element);
}

3.2.6. 出队

动画

1
2
3
4
5
6
7
8
/**
 * 出队
 *
 * @return E
 */
public E deQueue() {
    return list.remove(0);
}

3.2.7. 获取队列的头元素

1
2
3
4
5
6
7
8
/**
 * 获取队列的头元素
 *
 * @return E
 */
public E front() {
    return list.get(0);
}

3.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
public class BaseQueueTest {

    private BaseQueue<Integer> queue;

    @BeforeEach
    public void setup() {
        queue = new BaseQueue<>();
    }

    @Test
    public void testEnqueueAndSize() {
        queue.enQueue(5);
        queue.enQueue(10);
        Assertions.assertEquals(2, queue.size());
    }

    @Test
    public void testDequeueAndFront() {
        queue.enQueue(5);
        queue.enQueue(10);
        Assertions.assertEquals(5, queue.front());
        Assertions.assertEquals(5, queue.deQueue());
        Assertions.assertEquals(1, queue.size());
        Assertions.assertEquals(10, queue.front());
    }

    @Test
    public void testIsEmptyAndClear() {
        Assertions.assertTrue(queue.isEmpty());
        queue.enQueue(5);
        queue.enQueue(10);
        Assertions.assertFalse(queue.isEmpty());
        queue.clear();
        Assertions.assertTrue(queue.isEmpty());
    }
    
}

3.4. 实战练习

3.4.1. 用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

需求

image-20231122210429658

实现思路

  • 首先，准备两个栈。inStack、outStack
  • 然后，入队时，将元素放入 inStack 栈中。
  • 最后，出队(pop) 和获取栈顶元素(peek) 时，需要考虑如下两个问题：
    • outStack 为空：直接将 inStack 栈中的所有元素 push 到 outStack ，然后再从 outStack 弹出。
    • outStack 不为空：直接将 outStack 中的元素弹出。

image-20231122213417333

实现代码

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
class MyQueue {

    private Stack<Integer> inStack;

    private Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    public void push(Integer x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

4. 双端队列

双端队列本质上也是队列的一种，本质意思就是元素可以从队头和队尾进行入队和出队。

image-20231122214137331

4.1. 接口设计

image-20231122220112705

  • DeQueue<E>.java

我们的普通队列主要是基于链表进行实现，所以还是要基于以前的代码。

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
/**
 * 双端队列
 */
public class DeQueue<E> {

    private LinkedList<E> linkedList = new LinkedList<>();

    // 元素数量
    public int size() {}

    // 是否为空
    public boolean isEmpty() {}

    // 从队尾入队
    public void enQueueRear(E element) {}

    // 从队尾出队
    public E deQueueRear() {}

    // 从队头入队
    public void enQueueFront(E element) {}

    // 从队头出队
    public E deQueueFront() {}

    // 获取队列的头元素
    public E front() {}

    // 获取队列的尾元素
    public E rear() {}
    
}

4.2. 代码实现

4.2.1. 初始化成员变量

1
private List<E> linkedList = new LinkedList<>();

4.2.2. 元素的数量

1
2
3
4
5
6
7
/**
 * 元素数量
 * @return
 */
public int size() {
    return linkedList.size();
}

4.2.3. 是否为空

1
2
3
4
5
6
7
/**
 * 是否为空
 * @return
 */
public boolean isEmpty() {
    return linkedList.isEmpty();
}

4.2.4. 从队尾入队

1
2
3
4
5
6
7
8
/**
 * 从队尾出队
 *
 * @return E
 */
public E deQueueRear() {
    return linkedList.remove(size() - 1);
}

4.2.5. 从队头入队

1
2
3
4
5
6
7
8
/**
 * 从队头出队
 *
 * @return E
 */
public E deQueueFront() {
    return linkedList.remove(0);
}

4.2.6. 获取队列的头元素

1
2
3
4
5
6
7
8
/**
 * 获取队列的头元素
 *
 * @return E
 */
public E front() {
    return linkedList.get(0);
}

4.2.7. 获取队列的尾元素

1
2
3
4
5
6
7
8
/**
 * 获取队列的尾元素
 *
 * @return E
 */
public E rear() {
    return linkedList.get(size() - 1);
}

4.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
public class DeQueueTest {

    @Test
    public void testEmptyQueue() {
        DeQueue<Integer> queue = new DeQueue<>();
        
        assertEquals(0, queue.size());
        assertTrue(queue.isEmpty());
        
        // Ensure dequeue operations on an empty queue throw exceptions or return expected values
        assertThrows(IndexOutOfBoundsException.class, queue::deQueueFront);
        assertThrows(IndexOutOfBoundsException.class, queue::deQueueRear);
    }

    @Test
    public void testEnqueueDequeue() {
        DeQueue<String> queue = new DeQueue<>();

        queue.enQueueRear("First");
        queue.enQueueFront("New First");

        assertEquals(2, queue.size());
        assertFalse(queue.isEmpty());
        assertEquals("New First", queue.deQueueFront());
        assertEquals("First", queue.deQueueRear());
        assertTrue(queue.isEmpty());
    }

    @Test
    public void testFrontRear() {
        DeQueue<Character> queue = new DeQueue<>();

        queue.enQueueRear('A');
        queue.enQueueRear('B');
        queue.enQueueFront('C');
        queue.enQueueFront('D');

        assertEquals('D', queue.front());
        assertEquals('B', queue.rear());
    }

    @Test
    public void testBoundaryConditions() {
        DeQueue<Integer> queue = new DeQueue<>();

        // Single element queue
        queue.enQueueRear(42);
        assertEquals(42, (int) queue.deQueueFront());
        assertTrue(queue.isEmpty());

        // Enqueue a large number of elements and dequeue them one by one
        for (int i = 0; i < 1000; i++) {
            queue.enQueueRear(i);
        }

        for (int i = 0; i < 1000; i++) {
            assertEquals(i, (int) queue.deQueueFront());
        }
        assertTrue(queue.isEmpty());
    }
}

5. 循环队列

循环队列：就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

底层可以通过数组进行扩容，实现数据的入队和出队，元素从 rear 指向的位置入队，front 指向的位置出队。

数据结构：循环队列- 子烁爱学习- 博客园

5.1. 接口设计

目前我们通过动态数组实现循环队列

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
/**
 * 队列
 *
 * @param <E>
 */
public class CircleQueue<E> {
    // 记录队头元素的索引
    private int front;
    
    // 当前队列存储的元素个数
    private int size;
    
    // 用来存储元素的数组
    private E[] elements;
    
    // 元素的数量
    public int size(){}

    // 是否为空
    public boolean isEmpty(){}

    // 入队
    public void enQueue(E element){}

    // 出队
    public E deQueue(){}

    // 获取队列的头元素
    public E front(){}

}

5.2. 代码实现

5.2.1. 初始化成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@SuppressWarnings("unchecked")
public class CircleQueue<E> {

    // 数组大小
    private int size;

    // 头元素的索引
    private int front;

    // 数组
    private E[] elements;

    // 数组容量
    private static final int DEFAULT_CAPACITY = 10;

    // 初始化构造方法
    public CircleQueue() {
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

}

5.2.2. 元素的数量

与数组保持一致

1
2
3
4
5
6
7
8
/**
 * 元素的数量
 *
 * @return int
 */
public int size() {
    return size;
}

5.2.3. 队列是否为空

1
2
3
4
5
6
7
8
/**
 * 队列是否为空
 *
 * @return boolean
 */
public boolean isEmpty() {
    return size == 0;
}

5.2.4. 入队

入队：入队的其实就是往最后一个元素添加元素，由于我们时循环链表，需要考虑的问题就比较多了。

问题一：如果是在最后一个位置进行入队，那么元素应该需要添加到队列的第一个元素。

image-20231123175925570

问题二：由于动态数组的默认容量是 10 , 当队列满了的时候就需要考虑扩容了。

image-20231123211440014

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 入队
 *
 * @param element 元素
 */
public void enQueue(E element) {
    // 扩容
    ensureCapacity(size + 1);

    elements[index(size)] = element;
    size++;
}
5.2.4.1. 获取下一个元素的索引

这个是对动态数组到了最后一个元素时，在添加元素时就需要获取当前元素的索引

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 获取下一个元素的索引
 *
 * @param index 索引
 * @return
 */
private int index(int index) {
    // case1(使用 % 效率低): (front + index) % elements.length
    // case2: index - (elements.length > index ? 0 : elements.length);
    index += front;
    return index - (elements.length > index ? 0 : elements.length);
}
5.2.4.2. 数组扩容

当数组的容量满了之后就需要进行扩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 数组扩容
 *
 * @param capacity 当前容量
 */
@SuppressWarnings("unchecked")
private void ensureCapacity(int capacity) {
    if (capacity - elements.length > 0) {
        int newCapacity = capacity + (capacity >> 1);
        E[] newElement = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElement[i] = elements[index(i)];
        }
        elements = newElement;
        front = 0;
    }
}

5.2.5. 出队

出队是比较简单的，我们只需要将 front 索引指向的元素弹出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 出队
 *
 * @return E
 */
public E deQueue() {
    if (size <= 0) {
        throw new IndexOutOfBoundsException("This Circle is null");
    }
    E element = elements[front];
    elements[front] = null;
    front = index(1);
    size--;
    return element;
}

5.2.6. 获取队列的头元素

front 指向的元素就是头元素

1
2
3
4
5
6
7
8
9
/**
 * 获取队列的头元素
 */
public E front() {
    if (size <= 0) {
        throw new IndexOutOfBoundsException("This Circle is null");
    }
    return elements[front];
}

5.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
public class CircleQueueTest {

    @Test
    public void testEmptyQueue() {
        CircleQueue<Integer> queue = new CircleQueue<>();
        
        assertTrue(queue.isEmpty());
        assertEquals(0, queue.size());
        
        assertThrows(IndexOutOfBoundsException.class, queue::deQueue);
        assertThrows(IndexOutOfBoundsException.class, queue::front);
        System.out.println("queue = " + queue);
    }

    @Test
    public void testEnqueueAndDequeue() {
        CircleQueue<String> queue = new CircleQueue<>();

        queue.enQueue("One");
        queue.enQueue("Two");
        queue.enQueue("Three");

        assertEquals(3, queue.size());
        assertFalse(queue.isEmpty());
        assertEquals("One", queue.front());

        assertEquals("One", queue.deQueue());
        assertEquals("Two", queue.deQueue());
        assertEquals("Three", queue.deQueue());

        assertTrue(queue.isEmpty());
        assertEquals(0, queue.size());
        assertThrows(IndexOutOfBoundsException.class, queue::deQueue);
        assertThrows(IndexOutOfBoundsException.class, queue::front);
        System.out.println("queue = " + queue);
    }

    @Test
    public void testQueueResize() {
        CircleQueue<Integer> queue = new CircleQueue<>();

        int initialCapacity = 20;
        for (int i = 0; i < initialCapacity; i++) {
            queue.enQueue(i);
        }
        System.out.println("queue = " + queue);
        assertEquals(initialCapacity, queue.size());

        for (int i = 0; i < initialCapacity; i++) {
            assertEquals(i, queue.deQueue());
        }

        System.out.println("queue = " + queue);
        assertTrue(queue.isEmpty());
        assertEquals(0, queue.size());
    }

    // Add more test cases for boundary conditions, concurrent access, and exceptions if needed
}

6. 参考博文