玩转数据结构之队列

0. 序言

• 队列也是一种线性结构
• 相比数组，队列对应的操作是数组的子集
• 只能从一端（队尾）添加元素，只能从另一端（队首）取出元素

这篇文章会用之前的数组类Array实现一个底层为数组的队列ArrayQueue。建议在阅读本篇文章之前，先阅读关于动态数组类Array这篇文章：https://www.jianshu.com/p/02bbc13b5e5f 当然对数组了解比较深入的，可以直接阅读本篇。

1. 特点

• 队列是一种先进先出的数据结构——First In First Out（FIFO）

  
  队列

2. 实现

Queue<E>

• void enqueue(E)：入队
• E dequeue( )：出队
• E getFront( )：查看队首的元素
• int getSize( )：查询队列元素个数
• boolean isEmpty( )：判断队列是否为空

3. 设计

队列的实现

定义一个基于数组的队列，实现接口Queue<E>中的方法。

4. 代码

• 定义接口类Queue<E>

public interface Queue<E> {
    void enqueue(E e);
    E dequeue();
    E getFront();
    int getSize();
    boolean isEmpty();
}

• 定义接口Queue<E>的实现类ArrayQueue<E>

public class ArrayQueue<E> implements Queue<E>{

    private Array<E> array;

    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayQueue(){
        array = new Array<>();
    }

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

        @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue:  ");
        res.append("font [");
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

基于动态数组实现，这个队列具备了动态数组扩容和缩容的功能。

public class Test_ArrayQueue {
    public static void main(String[] args){
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);
            if (i%3==2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

Queue:  font [0] tail
Queue:  font [0, 1] tail
Queue:  font [0, 1, 2] tail
Queue:  font [1, 2] tail
Queue:  font [1, 2, 3] tail
Queue:  font [1, 2, 3, 4] tail
Queue:  font [1, 2, 3, 4, 5] tail
Queue:  font [2, 3, 4, 5] tail
Queue:  font [2, 3, 4, 5, 6] tail
Queue:  font [2, 3, 4, 5, 6, 7] tail
Queue:  font [2, 3, 4, 5, 6, 7, 8] tail
Queue:  font [3, 4, 5, 6, 7, 8] tail
Queue:  font [3, 4, 5, 6, 7, 8, 9] tail

从结果可知，添加三个元素就从队首取出一个元素，代码正确。

5. 复杂度分析

数组队列的复杂度
① 入队的操作的均摊复杂度为O(1)
如果对均摊复杂度不了解，可以跳转阅读这篇文章：https://www.jianshu.com/p/59f380c6ffcd
② 出队的操作的时间复杂度为O(n)
每次都会取出数组的第一个元素，需要搬移数据，可见性能不高。那如何提高性能呢？请关注下一篇关于循环队列的文章：https://www.jianshu.com/p/52d07a02aa97

6. 后续

如果大家喜欢这篇文章，欢迎点赞！
如果想看更多 数据结构 方面的文章，欢迎关注!