Java实现队列的三种常用方法

数组实现

数组实现队列的方法是，在一个数组中，从头部进入，从尾部出去。它的入队操作是在数组末尾添加一个新的元素，出队操作是移除数组的第一个元素。

public class ArrayQueue {
    private int[] array;
    private int front;
    private int rear;
 
    public ArrayQueue(int capacity) {
        this.array = new int[capacity];
    }
 
    /**
     * 入队
     */
    public void enQueue(int element) {
        if (rear == array.length) {
            throw new IndexOutOfBoundsException("队列已满！");
        }
        array[rear++] = element;
    }
 
    /**
     * 出队
     */
    public int deQueue() {
        if (front == rear) {
            throw new IndexOutOfBoundsException("队列为空！");
        }
        return array[front++];
    }
 
    public void output() {
        for (int i = front; i < rear; i++) {
            System.out.println(array[i]);
        }
    }
}

链表实现

链表实现队列的方法是，在一个链表中，从头部进入，从尾部出去。它的入队操作是在链表末尾添加一个新的节点，出队操作是移除链表的第一个节点。

public class LinkedListQueue {
    private Node head;
    private Node tail;
 
    private class Node {
        private int data;
        private Node next;
 
        public Node(int data) {
            this.data = data;
        }
    }
 
    /**
     * 入队
     */
    public void enQueue(int element) {
        if (tail == null) {
            Node newNode = new Node(element);
            head = newNode;
            tail = newNode;
        } else {
            tail.next = new Node(element);
            tail = tail.next;
        }
    }
 
    /**
     * 出队
     */
    public int deQueue() {
        if (head == null) {
            throw new IndexOutOfBoundsException("队列为空！");
        }
        int value = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return value;
    }
 
    public void output() {
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }
}

循环队列实现

循环队列实现队列的方法是，在一个数组中，从头部进入，从尾部出去。它的入队操作是在数组末尾添加一个新的元素，出队操作是移除数组的第一个元素。当数组满的时候，重新从头开始存储，这样就可以循环利用数组空间，节省空间。

public class CircularQueue {
    private int[] array;
    private int front;
    private int rear;
 
    public CircularQueue(int capacity) {
        this.array = new int[capacity];
    }
 
    /**
     * 入队
     */
    public void enQueue(int element) {
        if ((rear + 1) % array.length == front) {
            throw new IndexOutOfBoundsException("队列已满！");
        }
        array[rear] = element;
        rear = (rear + 1) % array.length;
    }
 
    /**
     * 出队
     */
    public int deQueue() {
        if (rear == front) {
            throw new IndexOutOfBoundsException("队列为空！");
        }
        int value = array[front];
        front = (front + 1) % array.length;
        return value;
    }
 
    public void output() {
        for (int i = front; i != rear; i = (i + 1) % array.length) {
            System.out.println(array[i]);
        }
    }
}