Java实现队列

队列是典型的FIFO数据结构。入队（队尾添加），出队(队首删除)。

定义队列接口

public interface Queue<T> {

    boolean enQueue(T t);

    T deQueue();

    int size();
}

数组实现队列

public class MyArrayQueue<T> implements Queue<T> {
    private final int capacity;
    private int size;
    private final T[] list;
    private int head;
    private int tail;

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

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

    @Override
    public boolean enQueue(T t) {
        if (size >= capacity) {
            return false;
        }
        list[tail++] = t;
        tail = tail % capacity;
        size++;
        return true;
    }

    @Override
    public T deQueue() {
        if (size < 0) {
            return null;
        }
        T remove = list[head++];
        head = head % capacity;
        size--;
        return remove;
    }

    @Override
    public int size() {
        return size;
    }

链表实现队列

public class MyListQueue<T> implements Queue<T> {
    private int size;
    private final int capacity;
    private final ListNode<T> head = new ListNode<>();
    private ListNode<T> tail = head;

    public MyListQueue() {
        this.capacity = 10;
    }

    public MyListQueue(int capacity) {
        this.capacity = capacity;
    }

    @Override
    public boolean enQueue(T t) {
        if (size >= capacity) {
            return false;
        }
        ListNode<T> newNode = new ListNode<>(t, tail.next);
        tail.next = newNode;
        tail = newNode;
        size++;
        return true;
    }

    @Override
    public T deQueue() {
        if (size <= 0) {
            return null;
        }
        ListNode<T> next = head.next;
        head.next = next.next;
        size--;
        return next.data;
    }

    @Override
    public int size() {
        return size;
    }

    static class ListNode<T> {
        T data;
        ListNode<T> next;

        public ListNode() {
        }

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

测试

public static void main(String[] args) {
        //        Queue<Integer> queue = new MyArrayQueue<>(3);
        Queue<Integer> queue = new MyListQueue<>(3);
        queue.enQueue(1);
        queue.enQueue(2);
        queue.enQueue(3);
        queue.enQueue(4);
        queue.enQueue(5);
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        queue.enQueue(21);
        System.out.println(queue.deQueue());
        queue.enQueue(22);
        queue.enQueue(23);
        queue.enQueue(24);

        while (queue.size() > 0) {
            System.out.println(queue.deQueue());
        }
    }