数据结构——队列@慕课网原创_慕课网

队列具有先进先出（FIFO）的特性。队列是在列表的基础上，限制了插入只能在队首，删除只能在队尾。所以队列底层同样有两种实现方式：数组队列和链队列。不同的是为了减小空间的浪费，数组队列一般可以把数组的首尾相连，组成一个循环队列。

队列接口

public interface IQueue<T> {
    void offer(T data); // 入队
    T peek(); // 取队首元素
    T poll(); // 出队
    int size(); // 队列长度
    boolean isEmpty(); // 队列判空
}

循环队列

源码
 测试类源码

/**
 * 数组实现的循环队列
 */
public class MyArrayQueue<T> implements IQueue<T> {

    private T[] datas; // 存放数据的数组
    private int capacity; // 数组容量
    private int count = 0; // 计数，用于计算长度
    private int top = 0; // 队首位置
    private int tail = -1; // 队尾的上一个位置

    public MyArrayQueue(int capacity) {
        this.capacity = capacity;
        this.datas = (T[]) new Object[capacity];
    }

    @Override
    public void offer(T data) {
        if (count == capacity)
            throw new RuntimeException("队列已满");
        tail = (tail + 1) % capacity;
        datas[tail] = data;
        count++;
    }

    @Override
    public T peek() {
        if (isEmpty())
            throw new RuntimeException("队列为空");
        return datas[top];
    }

    @Override
    public T poll() {
        if (isEmpty())
            throw new RuntimeException("队列为空");
        T res = datas[top];
        top = (top + 1) % capacity;
        count--;
        return res;
    }

    @Override
    public int size() {
        return this.count;
    }

    @Override
    public boolean isEmpty() {
        return this.count == 0;
    }
}

链队列

链队列与链表一样，使用了私有的Node类辅助。但不需要链表私有的getNode方法。
源码
 测试类源码

public class MyLinkedQueue<T> implements IQueue<T> {

    private class Node {
        T data;
        Node next;

        Node() {
        }

        Node(T data) {
            this.data = data;
        }

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node top = new Node(); // 队首指针，top.next为队首
    private Node tail = top; // 队尾指针,tail为队尾
    private int count = 0;

    @Override
    public void offer(T data) {
        tail.next = new Node(data);
        tail = tail.next;
        count++;
    }

    @Override
    public T peek() {
        if (isEmpty())
            throw new RuntimeException("队列为空");
        return top.next.data;
    }

    @Override
    public T poll() {
        if (isEmpty())
            throw new RuntimeException("队列为空");
        T res = top.next.data;
        top = top.next;
        count--;
        return res;
    }

    @Override
    public int size() {
        return this.count;
    }

    @Override
    public boolean isEmpty() {
        return this.count == 0;
    }
}

总结

从源码上分析，数组队列与链队列的入队、出队操作都是O(1)，数组队列更省空间，但不易扩展。

数据结构——队列原创