本文共 3658 字，大约阅读时间需要 12 分钟。

顺序队列的问题：

我们在实现顺序栈时使用头指针“front”和尾指针“rear”分别进行出队和入队操作，但普通的队列如上图所示，会发生“假溢出”现象，所以我们通常将数组弄成一个环状，即队头和队尾相连，这样就形成了“循环队列”，同时也解决了“假溢出”现象。循环队列是改进版的顺序队列。

对于普通队列的push或pop我们只需要对尾指针或头指针进行自增操作即可，但是循环队列我们就不能单纯的进行自增，当front或rear=maxSize-1时我们就不能进行自增操作了，比如一个队列尾长度为4的数组datas[4]，那么当front或rear需要在0,1,2,3之间进行循环“推进”，以此达到循环队列的效果。所以我们可以使用rear = （rear+1）%maxSize ；front = （front+1）%maxSize ；公式进行指针计算。

需要注意的是：队空状态的条件为：front = rear。而如果整个队列全部存满数据那么，队满的条件也是front = rear；所以循环队列需要损失一个存储空间，如下图

public class myQueue {        public int size = 10;    // 队列大小        public int count = 0;    // 计数        public int datas[];            public int front;        // 头指针        public int rear;         // 尾指针        public myQueue(int size) {            this.size = size;            datas = new int[10];            count = 0;            front = 0;            rear = 0;        }        public boolean enqueue(int data) {            if (isFull()) {                return false;            }            datas[rear] = data;            rear = (rear + 1) % size;            count++;            return true;        }        public int dequeue() throws Exception {            if (isEmpty()) {                throw new Exception("empty");            }            int data = datas[front];            front = (front + 1) % size;            count--;            return data;        }        /**         * 循环队列空队和满队条件都是front == rear解决该问题有几种判断如下         * 1.循环队列损失一个存储空间         * 2.设计一个计数器count，统计队列中的元素个数。此时，队列满的判断条件为：count > 0 && rear == front ；队列空的判断条件为count == 0。         *         * @return         */        public boolean isFull() {            return (rear + 1) % size == front;        }        public boolean isEmpty() {            return front == rear;        }        public int getFront() throws Exception {            if (!isEmpty()) {                throw new Exception("empty");            }            return datas[front];        }    }    class producer implements Runnable {        @Override        public void run() {            while (true) {                synchronized (myQueue) {                    while (myQueue.isFull()) {                        myQueue.notify();                        Log.i(TAG, "run: 队满！");                        try {                            myQueue.wait();                        } catch (InterruptedException e) {                            e.printStackTrace();                        }                    }                    myQueue.enqueue(1);                    Log.i(TAG, "run: 生产1，队列长度： " + myQueue.count);                    myQueue.notify();                    try {                        Thread.sleep(1000);                    } catch (InterruptedException e) {                        e.printStackTrace();                    }                }            }        }    }    class consumer implements Runnable {        @Override        public void run() {            while (true) {                synchronized (myQueue) {                    while (myQueue.isEmpty()) {                        myQueue.notify();                        Log.i(TAG, "run: 队空！");                        try {                            myQueue.wait();                        } catch (InterruptedException e) {                            e.printStackTrace();                        }                    }                    try {                        myQueue.dequeue();                        Log.i(TAG, "run: 消费1，队列长度： " + myQueue.count);                        myQueue.notify();                        Thread.sleep(500);                    } catch (Exception e) {                        e.printStackTrace();                    }                }            }        }    }

转载地址：http://tflcn.baihongyu.com/