本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
知识点
- 环形缓冲区
题目
1.3.39 环形缓冲区。环形缓冲区，又称为环形队列，是一种定长为 N 的先进先出的数据结构。它在进程间的异步数据传输或记录日志文件时十分有用。当缓冲区为空时，消费者会在数据存入缓冲区前等待；当缓冲区满时，生产者会等待数据存入缓冲区。为 RingBuffer 设计一份 API 并用（回环）数组将其实现。
1.3.39 Ring buffer. A ring buffer, or circular queue, is a FIFO data structure of a fixed size N. It is useful for transferring data between asynchronous processes or for storing log files. When the buffer is empty, the consumer waits until data is deposited; when the buffer is full, the producer waits to deposit data. Develop an API for a RingBuffer and an implementation that uses an array representation (with circular wrap-around).
分析
圆形缓冲区（circular buffer）
也称作圆形队列（circular queue），循环缓冲区（cyclic buffer），环形缓冲区（ring buffer），是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构，适合缓存数据流。
生产者消费者问题
（英语：Producer-consumer problem），也称有限缓冲问题（英语：Bounded-buffer problem），是一个多线程同步问题的经典案例。该问题描述了共享固定大小缓冲区的两个线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。 要解决该问题，就必须让生产者在缓冲区满时休眠（要么干脆就放弃数据），等到下次消费者消耗缓冲区中的数据的时候，生产者才能被唤醒，开始往缓冲区添加数据。同样，也可以让消费者在缓冲区空时进入休眠，等到生产者往缓冲区添加数据之后，再唤醒消费者。通常采用进程间通信的方法解决该问题，常用的方法有信号灯法[1]等。如果解决方法不够完善，则容易出现死锁的情况。出现死锁时，两个线程都会陷入休眠，等待对方唤醒自己。该问题也能被推广到多个生产者和消费者的情形。
回到这道题，网上的解法有很多，因为这道题可以做的很简单，也可以做的很复杂。这篇文章Java Ring Buffer大家可以借鉴一下，现在我来给出几个答案。
分析
本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅
答案
API
| 返回类型 | 函数 | 备注 |
|---|---|---|
| boolean | reset() | 重新设置 |
| int | size() | 大小 |
| boolean | put(Item x) | 存入缓存 |
| Item | take() | 读取 |
public class RingBuffer<Item> {
public Item[] a = null;
public int writePos = 0;
public int readPos = 0;
public boolean flipped = false; // the flip marker
public RingBuffer(int cap) {
this.a = (Item[]) new Object[cap];
}
public void reset() {
this.writePos = 0;
this.readPos = 0;
this.flipped = false;
}
public int size() {
return a.length;
}
public int available() {
if (!flipped) {
return writePos - readPos;
}
return size() - readPos + writePos;
}
public int remainingCapacity() {
if (!flipped) {
return size() - writePos;
}
return readPos - writePos;
}
public boolean put(Item x) {
if (!flipped) {
if (writePos == size()) {
writePos = 0;
flipped = true;
if (writePos < readPos) {
a[writePos++] = x;
return true;
} else {
return false;
}
} else {
a[writePos++] = x;
return true;
}
} else {
if (writePos < readPos) {
a[writePos++] = x;
return true;
} else {
return false;
}
}
}
public Item take() {
if (!flipped) {
if (readPos < writePos) {
return a[readPos++];
} else {
return null;
}
} else {
if (readPos == size()) {
readPos = 0;
flipped = false;
if (readPos < writePos) {
return a[readPos++];
} else {
return null;
}
} else {
return a[readPos++];
}
}
}
}
这个方案中有个标记为 flipped，用于标记是否已经被读取过一次。
测试用例
public static void main(String[] args){
int capacity = 10;
RingBuffer<String> ringBuffer = new RingBuffer<String>(capacity);
/*******************测试用例1*************************/
for (int i = 0; i < capacity; i++) {
String inputItem = i+"";
boolean putSuccess = ringBuffer.put(inputItem);
System.out.println(putSuccess ? "插入" + inputItem + "成功" : "插入" + inputItem + "失败" );
}
/*******************测试用例2*************************/
for (int i = 0; i < capacity + 1; i++) {
if (i == capacity - 1) {
String takeItem = ringBuffer.take();
System.out.println("取出" + takeItem + "成功");
}
if (i == capacity) {
String takeItem = ringBuffer.take();
System.out.println("取出" + takeItem + "成功");
}
String inputItem = i+"";
boolean putSuccess = ringBuffer.put(inputItem);
System.out.println(putSuccess ? "插入" + inputItem + "成功" : "插入" + inputItem + "失败" );
}
}
代码索引
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
