本系列博客習(xí)題來自《算法(第四版)》乾蛤，算是本人的讀書筆記邑滨，如果有人在讀這本書的日缨，歡迎大家多多交流。為了方便討論掖看，本人新建了一個微信群(算法交流)匣距，想要加入的，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝哎壳。另外毅待，本人的個人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論

算法(第4版)

知識點

• 環(huán)形緩沖區(qū)

題目

1.3.39 環(huán)形緩沖區(qū)归榕。環(huán)形緩沖區(qū)尸红，又稱為環(huán)形隊列，是一種定長為 N 的先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)刹泄。它在進(jìn)程間的異步數(shù)據(jù)傳輸或記錄日志文件時十分有用外里。當(dāng)緩沖區(qū)為空時，消費(fèi)者會在數(shù)據(jù)存入緩沖區(qū)前等待特石；當(dāng)緩沖區(qū)滿時盅蝗，生產(chǎn)者會等待數(shù)據(jù)存入緩沖區(qū)。為 RingBuffer 設(shè)計一份 API 并用（回環(huán)）數(shù)組將其實現(xiàn)姆蘸。

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).

分析

圓形緩沖區(qū)（circular buffer）
也稱作圓形隊列（circular queue）墩莫，循環(huán)緩沖區(qū)（cyclic buffer）芙委，環(huán)形緩沖區(qū)（ring buffer），是一種用于表示一個固定尺寸贼穆、頭尾相連的緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)题山，適合緩存數(shù)據(jù)流兰粉。

生產(chǎn)者消費(fèi)者問題
（英語：Producer-consumer problem）故痊，也稱有限緩沖問題（英語：Bounded-buffer problem），是一個多線程同步問題的經(jīng)典案例玖姑。該問題描述了共享固定大小緩沖區(qū)的兩個線程——即所謂的“生產(chǎn)者”和“消費(fèi)者”——在實際運(yùn)行時會發(fā)生的問題愕秫。生產(chǎn)者的主要作用是生成一定量的數(shù)據(jù)放到緩沖區(qū)中，然后重復(fù)此過程焰络。與此同時戴甩，消費(fèi)者也在緩沖區(qū)消耗這些數(shù)據(jù)。該問題的關(guān)鍵就是要保證生產(chǎn)者不會在緩沖區(qū)滿時加入數(shù)據(jù)闪彼，消費(fèi)者也不會在緩沖區(qū)中空時消耗數(shù)據(jù)甜孤。 要解決該問題，就必須讓生產(chǎn)者在緩沖區(qū)滿時休眠（要么干脆就放棄數(shù)據(jù)）畏腕，等到下次消費(fèi)者消耗緩沖區(qū)中的數(shù)據(jù)的時候缴川，生產(chǎn)者才能被喚醒，開始往緩沖區(qū)添加數(shù)據(jù)描馅。同樣把夸，也可以讓消費(fèi)者在緩沖區(qū)空時進(jìn)入休眠，等到生產(chǎn)者往緩沖區(qū)添加數(shù)據(jù)之后铭污，再喚醒消費(fèi)者恋日。通常采用進(jìn)程間通信的方法解決該問題，常用的方法有信號燈法[1]等嘹狞。如果解決方法不夠完善岂膳，則容易出現(xiàn)死鎖的情況。出現(xiàn)死鎖時磅网，兩個線程都會陷入休眠谈截，等待對方喚醒自己。該問題也能被推廣到多個生產(chǎn)者和消費(fèi)者的情形知市。

回到這道題傻盟，網(wǎng)上的解法有很多，因為這道題可以做的很簡單嫂丙，也可以做的很復(fù)雜娘赴。這篇文章Java Ring Buffer大家可以借鑒一下，現(xiàn)在我來給出幾個答案跟啤。

分析

本人所有簡書的算法文章詳細(xì)分析已經(jīng)移入小專欄：算法四習(xí)題詳解诽表，歡迎大家訂閱

答案

API

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++];
            }
        }
    }
}

這個方案中有個標(biāo)記為 flipped唉锌，用于標(biāo)記是否已經(jīng)被讀取過一次。

測試用例

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 + "失敗" );
    }
    
}

代碼索引

RingBuffer.java

廣告

我的首款個人開發(fā)的APP壁紙寶貝上線了竿奏，歡迎大家下載袄简。

壁紙寶貝