Java循环队列

顺序队列在有限的空间的入队操作会浪费较大的内存空间，如果在每次队满时进行入队操作中都去扩容有可能会造成内存溢出。

频繁的去移动元素的位置来维持空间，又会造成性能上的浪费。

循环队列就解决了顺序队列的这个问题，既不会造成内存浪费，又不会在入队时移动元素来造成性能浪费。

public class LoopArrayQueue {

    int[] data; // 队列元素

    int head; // 头指针指向真实头部数据的位置

    int tail; // 尾指针指向真实尾部数据+1的位置

    int size; // 队列的容量，真实的队列容量为size-1，因为要空出一个位置留给尾指针

    public LoopArrayQueue(int size) {
        data = new int[size];
        head = tail = 0;
        this.size = size;
    }

    
    public void push(int x) {
        if (!isFull()) {
            data[tail] = x;
            //如果当前尾部元素正好位于size的最大值
            //那么tail+1 会导致数组越界，又不能形成环形，所以需要取模运算
            tail = (tail + 1) % size; // ，
        }
    }

    
    public int pop() {
        if (isEmpty()) {
            return -1;
        }
        int var = data[head];
        head = (head + 1) % size; // 原因同尾部元素
        return var;
    }

    
    public boolean isFull() {
        if ((tail + 1) % size == head) {
            System.out.println("===========队列满了==========");
            return true;
        }
        return false;
    }

    
    public boolean isEmpty() {
        if (head == tail) {
            System.out.println("===========队列空了==========");
            return true;
        }
        return false;
    }

    
    public void print() {
        for (int i = 0; i < data.length; i++) {
            System.out.println("第" + i + "个元素是：" + data[i]);
        }
    }

    public static void main(String[] args) {
        LoopArrayQueue queue = new LoopArrayQueue(8);
        queue.push(1);
        queue.push(2);
        queue.push(3);
        queue.push(4);
        queue.push(5);
        queue.push(6);
        queue.push(7);
        queue.push(8);
        // ===============提示满了===============

        // ===============打印一下队列看一下顺序===============
        queue.print();

        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        // ===============提示空了===============

        // ===============此时指针都指向7的位置==============
        System.out.println("头部指针：：：" + queue.head);
        System.out.println("尾部指针：：：" + queue.tail);


        // ===============再来一轮==============

        queue.push(1);
        queue.push(2);
        queue.push(3);
        queue.push(4);
        queue.push(5);
        queue.push(6);
        queue.push(7);
        queue.push(8);
        // ===============提示满了===============

        // ===============打印一下队列看一下顺序===============
        queue.print();

        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        // ===============提示空了===============

        // ===============此时指针都指向6的位置==============
        System.out.println("头部指针：：：" + queue.head);
        System.out.println("尾部指针：：：" + queue.tail);

    }
}