java实现循环队列(生产者消费者)
顺序队列的问题:
我们在实现顺序栈时使用头指针“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();
}
}
}
}
}